21. Merge Two Sorted Lists

发表于 | 分类于 | 浏览 次

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

1
2
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

递归解法

递归的方法每次确定一个元素的位置，将问题规模减小1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }
        if(l2 == nullptr){
            return l1;
        }
        ListNode* newHead = nullptr;
        if(l1->val > l2->val){
            newHead = l2;
           newHead->next  = mergeTwoLists(l1, l2->next);
        }else{
            newHead = l1;
            newHead->next = mergeTwoLists(l1->next, l2);
        }
        return newHead;
    }
};

非递归解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == nullptr){
            return l2;
        }
        if(l2 == nullptr){
            return l1;
        }
        ListNode* p1 = l1;
        ListNode* p2 = l2;
        ListNode* pre = nullptr;
        ListNode* next = nullptr;
        ListNode* head = l1->val <= l2->val ? l1 : l2;
        while(p1 && p2){
            while(p1 && p1->val <= p2->val){
                pre = p1;
                p1 = p1->next;
            }
            next = p2->next;
            if(pre != nullptr){
                pre->next = p2;                
            }
            p2->next = p1;
            pre = p2;
            p2 = next;
        }
        if(p2 != nullptr){
            pre->next = p2;
        }
        return head;
    }
};