Merge Two Sorted Lists

Question

  1. Merge two sorted linked lists and return it as a new list.
  2. The new list should be made by splicing together the nodes of the first two lists.
  4. Example
  5. Given 1->3->8->11->15->null, 2->null , return 1->2->3->8->11->15->null

題解

此題為兩個鏈表的合併，合併後的表頭節點不一定，故應聯想到使用dummy節點。鏈表節點的插入主要涉及節點next指標值的改變，兩個鏈表的合併操作則涉及到兩個節點的next值變化，若每次合併一個節點都要改變兩個節點next的值且要對NULL指標做異常處理，勢必會異常麻煩。嗯，第一次做這題時我就是這麼想的… 下面看看相對較好的思路。

首先dummy節點還是必須要用到，除了dummy節點外還引入一個lastNode節點充當下一次合併時的頭節點。在l1或者l2的某一個節點為空指標NULL時，退出while循環，並將非空鏈表的頭部鏈接到lastNode->next中。

C++

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
  12.         ListNode *dummy = new ListNode(0);
  13.         ListNode *lastNode = dummy;
  14.         while ((NULL != l1) && (NULL != l2)) {
  15.             if (l1->val < l2->val) {
  16.                 lastNode->next = l1;
  17.                 l1 = l1->next;
  18.             } else {
  19.                 lastNode->next = l2;
  20.                 l2 = l2->next;
  21.             }
  23.             lastNode = lastNode->next;
  24.         }
  26.         // do not forget this line!
  27.         lastNode->next =  (NULL != l1) ? l1 : l2;
  29.         return dummy->next;
  30.     }
  31. };

源碼分析

  1. 異常處理，包含在dummy->next中。
  2. 引入dummy和lastNode節點，此時lastNode指向的節點為dummy
  3. 對非空l1,l2循環處理，將l1/l2的較小者鏈接到lastNode->next，往後遞推lastNode
  4. 最後處理l1/l2中某一鏈表為空退出while循環，將非空鏈表頭鏈接到lastNode->next
  5. 返回dummy->next，即最終的首指標

注意lastNode的遞推並不影響dummy->next的值，因為lastNode和dummy是兩個不同的指標變量。

Note 鏈表的合併為常用操作，務必非常熟練，以上的模板非常精煉，有兩個地方需要記牢。1. 循環結束條件中為條件與操作；2. 最後處理lastNode->next指標的值。

複雜度分析

最好情況下，一個鏈表為空，時間複雜度為 O(1). 最壞情況下，lastNode遍曆兩個鏈表中的每一個節點，時間複雜度為 O(l1+l2). 空間複雜度近似為 O(1).

Reference