LeetCode刷题日记（21. 合并两个有序链表）

21. 合并两个有序链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if (!l1 && !l2) return NULL;
    struct ListNode *dummy = calloc(1, sizeof(struct ListNode));
    struct ListNode *head = dummy;
    while (1) {
        if ( !l1 && !l2 ) {
            break;
        }
        if ( l1 && l2 ) {
            struct ListNode *tmp = calloc(1, sizeof(struct ListNode));
            if (l1->val <= l2->val) {
                tmp->val = l1->val;
                l1 = l1->next;
            } else {
                tmp->val = l2->val;
                l2 = l2->next;
            }
            tmp->next = NULL;
            head->next = tmp;
            head = tmp;
        }
        else if (l1 && !l2) {
            head->next = l1;
            break;
        } else if (!l1 && l2) {
            head->next = l2;
            break;
        }
    }
    return dummy->next;
}

对两个链表进行遍历，将较小的值保存到新的链表中，直到其中一个链表遍历完，剩下的一个链表因为已经排好序了，不需要再遍历，直接连在新链表之后就可以了。

一开始我觉得是可以用递归解决的，但是没想出来怎么做，看了看评论区发现了：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(l1==NULL)
        return l2;
    if(l2==NULL)
        return l1;
    if(l1->val < l2->val){
        l1->next = mergeTwoLists(l1->next,l2);
        return l1;
    }else{
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
}

递归的停止条件是l1或l2有一个为NULL，如果这两个有一个为NULL，说明为NULL的这个链表中的元素已经排好了，直接返回另一个链表的当前节点。

mergeTwoLists函数总是返回已经排列好的链表的头节点，在一开始，假如l1->val < l2->val，说明此时的l1->val是最小值，那么此时的l1也是最后所返回结果链表的头节点，此时的l1->val的位置相当于已经确定了，然后再对其他的元素进行排列（调用mergeTwoLists函数）