leetcode--21.合并兩個有序連結清單

1. 合并兩個有序連結清單

   将兩個有序連結清單合并為一個新的有序連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。

示例：

輸入：1->2->4, 1->3->4

輸出：1->1->2->3->4->4

思路一：疊代

建立頭結點，通過指針穿針引線，運用歸并排序的思路。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode newListHead(0);
        ListNode* pList = &newListHead;
        while (l1 && l2){
            if (l1->val <= l2->val){
                pList->next = l1;
                l1 = l1->next;
            }else {
                pList->next = l2;
                l2 = l2->next;
            }
            pList = pList->next;
        }
        pList->next = l1 ? l1 : l2;
        return newListHead.next;
    }
};
           

時間複雜度: O(m+n)，空間複雜度: O(1)

以下方法與思路一基本相同，不同點，保持兩個有序連結清單原來的節點連接配接，通過swap函數交換節點中value實作排序，最後記得通過指針連接配接兩個連結清單。

過程如下：

輸入：1->2->4, 1->3->4

l1: 1->2->4

l2: 1->3->4

1與1相同不交換

l1: 2->4

l2: 1->3->4

2比1大，swap後l1: 1->3->4，下一步l1 = l1->next;

l1: 3->4

l2: 2->4

3比2大，swap後l1: 2->4，下一步l1 = l1->next;

l1: 4

l2: 3->4

4比3大，swap後l1: 3->4，下一步l1 = l1->next;

l1: 4

l2: 4

4與4相同，l1周遊完，隻剩下l2: 4

pList->next = l1 ? l1 : l2;最後一個值為4的節點串連進來，完成！

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode newListHead(0);
        ListNode *pList = &newListHead;
        while(l1 && l2) {
            if(l1->val > l2->val) swap(l1, l2);
            pList->next = l1;
            l1 = l1->next;
            pList = pList->next;
        }
        pList->next = l1 ? l1 : l2;
        return newListHead.next;
    }
};
           

時間複雜度: O(m+n)，空間複雜度: O(1)

思路二：遞歸（歸并排序法思想）

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

時間複雜度: O(m+n)，空間複雜度: O(m+n)

參考連結：

LeetCode（21）：合并兩個有序連結清單–4種方法

https://www.cnblogs.com/ariel-dreamland/p/9133521.html