將兩個(gè)鏈表進(jìn)行合并是算法中常見(jiàn)的操作，簡(jiǎn)單的合并操作容易實(shí)現(xiàn)。但是更多的情況是鏈表通常是按照一定順序排列的，合并的時(shí)候也需要考慮合并后其中各個(gè)元素的排列問(wèn)題。這可以歸類為合并兩個(gè)有序鏈表的問(wèn)題，具體來(lái)說(shuō)就是：有兩個(gè)單向鏈表，它們的每個(gè)節(jié)點(diǎn)都有一個(gè)數(shù)字，且節(jié)點(diǎn)中的數(shù)字按照升序排列，現(xiàn)在需要合并這兩個(gè)鏈表，合并后仍然是按照升序排列，如下圖所示：

對(duì)于這個(gè)問(wèn)題，最直接的思路應(yīng)該是直接進(jìn)行合并，然后再對(duì)合并后的鏈表進(jìn)行排序。

雖然這個(gè)方法是可行的，但是這個(gè)方法并不是最好的，這個(gè)方法主要的耗時(shí)在于重新排序，它的時(shí)間復(fù)雜度是O（m+n）log（m+n），m和n分別是L1和L2鏈表的長(zhǎng)度，稍后我們會(huì)給出更加優(yōu)雅的方案以供討論。

在提出第二種方案之前，需要提一下可能會(huì)用到的一個(gè)“trick” — 虛擬節(jié)點(diǎn)（dummy node），也叫虛擬頭節(jié)點(diǎn)。虛擬節(jié)點(diǎn)是當(dāng)我們合并兩個(gè)鏈表時(shí)不知道哪個(gè)節(jié)點(diǎn)是新鏈表第一個(gè)節(jié)點(diǎn)時(shí)會(huì)用到，因?yàn)橐_保新鏈表的第一個(gè)元素最小，而這個(gè)元素可能是 l1 或 l2 第一個(gè)節(jié)點(diǎn)中的某一個(gè)。所以，暫時(shí)用虛擬節(jié)點(diǎn)作為新鏈表的起始節(jié)點(diǎn)，后面合并完畢后會(huì)刪除這個(gè)節(jié)點(diǎn)。

對(duì)于我們之前提到的這個(gè)問(wèn)題，我們會(huì)用到兩個(gè)指針 （指向鏈表第一個(gè)節(jié)點(diǎn)）、（指向鏈表第一個(gè)節(jié)點(diǎn)），前面提到的虛擬節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)（current node，用于循環(huán)，被初始化指向虛擬節(jié)點(diǎn)）。通過(guò)循環(huán)訪問(wèn)所有節(jié)點(diǎn)來(lái)構(gòu)成新的鏈表。在每次循環(huán)中，會(huì)比較兩個(gè)鏈表中和指向的節(jié)點(diǎn)的值，使當(dāng)前節(jié)點(diǎn)一直指向較小值節(jié)點(diǎn)的下一節(jié)點(diǎn)。如下圖：

在第一步中，指向的節(jié)點(diǎn)值為 2，指向節(jié)點(diǎn)值為 6, 因?yàn)?2 < 6，所以curr 指向 所指向的那個(gè)值為 2 的節(jié)點(diǎn)，然后指向下一節(jié)點(diǎn)，即指向節(jié)點(diǎn)值為 5 的節(jié)點(diǎn)，如下圖：

第二步中，指向的節(jié)點(diǎn)的值仍然小于指向的節(jié)點(diǎn)的值，所以 curr 繼續(xù)向后移動(dòng)指向節(jié)點(diǎn)值為 5 的節(jié)點(diǎn)，指向下一節(jié)點(diǎn), 即指向節(jié)點(diǎn)值為 7 的節(jié)點(diǎn)如下圖：

第三步中，指向的節(jié)點(diǎn)的值總算是大于指向的節(jié)點(diǎn)的值了，那么在這個(gè)時(shí)候要注意了, curr 該向哪里移動(dòng)呢？想一想。

需要注意代碼實(shí)現(xiàn) curr 的一次移動(dòng)時(shí)候，要先讓 curr 當(dāng)前指向的 node 的 next 指向 所指向的節(jié)點(diǎn), curr->next = p2。

然后執(zhí)行 curr = curr->next

curr 該移動(dòng)到當(dāng)前指向的節(jié)點(diǎn)，然后向后移動(dòng)，如下圖：

以此類推，直到或者指針移動(dòng)到鏈表的末端，因?yàn)槲覀冊(cè)诿看伪容^中都選擇較小的值，所以當(dāng)或者中任何一個(gè)指針指向鏈表末端，代表另外一個(gè)沒(méi)有還沒(méi)到達(dá)末端的鏈表的后序的值都比已到達(dá)末端的鏈表中最大的值要大，所以只需要將后續(xù)的節(jié)點(diǎn)追加到新的鏈表后即可。

代碼實(shí)現(xiàn)如下：

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

   // 結(jié)構(gòu)體的構(gòu)造函數(shù)，與類的構(gòu)造函數(shù)相同。不適用于 C 語(yǔ)言結(jié)構(gòu)體。
   // 冒號(hào)后面的是初始化列表，也就是給成員val初始化為傳入的參數(shù)x，next初始化為NULL 
   ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
   // 參數(shù)為 l1 和 l2 的頭節(jié)點(diǎn)地址
   ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {

       // 如果鏈表 l1 為空，直接返回 l2
       if (l1 == nullptr)
           return l2;
       
       // 如果鏈表 l2 為空，直接返回 l1
       if (l2 == nullptr)
           return l1;

       // 設(shè)置虛擬節(jié)點(diǎn) ，并初始化值為 -1，指針域?yàn)?空。
       // new ListNode(-1) 返回的地址賦值給 ListNode類型 的指針 h
       ListNode* h = new ListNode(-1);
       
       // 指針 curr 指向新鏈表虛擬節(jié)點(diǎn) h，用于進(jìn)行循環(huán)
       ListNode* curr = h;

       // 指針 p1 指向 l1 頭節(jié)點(diǎn)
       ListNode* p1 = l1;

       // 指針 p1 指向 l2 頭節(jié)點(diǎn)
       ListNode* p2 = l2;

       
       // C++11 新標(biāo)準(zhǔn)中引入了 nullptr 來(lái)聲明一個(gè)“空指針”,新標(biāo)準(zhǔn)建議使用 nullptr 代替 NULL 來(lái)聲明空指針。
       // 這里的意思是，當(dāng)指針 p1 和 p2 指向不為空的時(shí)候，執(zhí)行循環(huán)
       while (p1 != nullptr && p2 != nullptr)
       {
           // 如果 p1 指向節(jié)點(diǎn)的值 <= p2 指向節(jié)點(diǎn)的值
           if (p1->val <= p2->val)
           {
               // 指針 curr 指向 指針p1 所指向的節(jié)點(diǎn)，因?yàn)?p1 所指向的節(jié)點(diǎn)的值較小
               curr->next = p1;

               // 指針 p1 指向單鏈表中的下一個(gè)節(jié)點(diǎn)
               p1 = p1->next;
           }
           // 如果 p1 指向節(jié)點(diǎn)的值 > p2 指向節(jié)點(diǎn)的值
           else
           {
               // curr 指向值較小的那個(gè)節(jié)點(diǎn)
               curr->next = p2;

               // 在 l2 上繼續(xù)遍歷鏈表，并進(jìn)入下一次循環(huán)進(jìn)行比較
               p2 = p2->next;
           }

           // curr 指針移動(dòng)到 curr->next 所指向的節(jié)點(diǎn)
           curr = curr->next;

       }// 以此類推，直到 p1 或者 p2 指針移動(dòng)到鏈表的末端



       // 當(dāng) l1 和 l2 兩個(gè)之中有一個(gè)到了尾部，那么循環(huán)結(jié)束
       // 循環(huán)結(jié)束之后，需要判斷到底哪一個(gè)鏈表先到鏈表的末端


       // 如果是 l2 先到了鏈表末端，那么 p1 != nullptr
       // 所以 curr->next 指向 p1 
       // p1 后續(xù)節(jié)點(diǎn)已經(jīng)排好序了，故直接合并進(jìn)來(lái)就好
       if (p1 != nullptr)
       {
           curr->next = p1;
       }

       // 如果是 l1 先到了鏈表末端，那么 p2 != nullptr
       // 所以 curr->next 指向 p2 
       // p2 后續(xù)節(jié)點(diǎn)已經(jīng)排好序了，故直接合并進(jìn)來(lái)就好
       if (p2 != nullptr)
       {
           curr->next = p2;
       }

       // 新建一個(gè)鏈表節(jié)點(diǎn) retNode ，將虛擬節(jié)點(diǎn)指向的下一個(gè)節(jié)點(diǎn)（即新鏈表的頭節(jié)點(diǎn)）
       ListNode* retNode = h->next;

       // 刪除所設(shè)置的虛擬頭節(jié)點(diǎn)
       delete h;

       // 返回合并后的新鏈表，此時(shí)已經(jīng)沒(méi)有的虛擬節(jié)點(diǎn)。
       return retNode;
   }
};

今天便開(kāi)始踏上算法刷題之旅了，在此先立個(gè) Flag，希望自己能夠堅(jiān)持到明年拿到理想 Offer 的那一天！