21. Merge Two Sorted Lists

解題思路

本題的目標是不額外生成 linked list 的情況下，將兩個 linked list 合併。

這個問題可以分三個部分來解決。首先，如何處理開頭的 node？該問題可以由 dummy node 的概念解決，意思是額外 new 一個多個 node 出來，用它的 next 來指向 merged list 的 head。

再來是如何 merge？其實也很簡單，想像說每次都比較 list 的頭，看哪個值比較小就把上個 node 的 next 指過來，同時記得更新 current 指到哪，以及 list 往後指一個。

最後是 while 迴圈結束時，並不代表事情做完了，兩個 list 還會有一個 list 沒空掉。那其實直接把 next 指向剩下的 list 就好了。

程式碼

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode dummpy;
        ListNode* current = &dummpy;

        while(list1 != nullptr && list2 != nullptr)
        {
            if(list1->val < list2->val)
            {
                current->next = list1;
                list1 = list1->next;
            }
            else
            {
                current->next = list2;
                list2 = list2->next;
            }
            current = current->next;
        }
        if(list1 != nullptr)
            current->next = list1;
        else if(list2 != nullptr)
            current->next = list2;
        return dummpy.next;
    }
};