#21. Merge Two Sorted Lists
題目描述
給你兩個鏈結串列(Linked List)List1和List2。
將兩個串列合併為一個整理過的串列，該串列必須由前兩個串列的節點(Nodes)拼接而成。
回傳整理後的串列的第一個節點。
限制條件
- 兩個初始串列的節點數量為[0, 50]。
- -100 <= 節點的值 <= 100
- 兩個初始串列的節點都是非遞減(non-decreasing)排列。
- 合併後的串列必須整理過，題目描述中沒有指定排序的順序，但是從範例1中可以觀察到順序是由小到大排列的，所以指的是合併後的串列節點需同樣為非遞減排列。
解題思路
這一題我們把它想像成在串珠子，假設你面前有兩串珠子，都按照小到大的順序，請你按照大小從小排到大，你該怎麼做呢？
步驟：
- 先從兩串的第一個珠子的編號做比較，選出比較小的珠子作為合併後的珠串的頭，比較大的那串先保留。
- 接下來從較小的那顆珠子的下一顆珠子，和保留的珠串的排最前面的珠子做比較，同樣選出比較小的那顆。
- 將較小的那顆接在前一輪被選出的珠子後面，繼續下一輪的比較，重複第2、3步，直到其中一方的最後一顆珠子沒了。
- 如果保留的那串還有剩下的珠子，就把它接到合併後珠串後面，完成整個合併。
範例： A: 1->2->4, B: 1->3->4
A1 A2 A3 B1 B2 B3
比較A、B的第一個數字，選出較小的，一樣的情況下，根據訂下的判斷規則選擇其中一個，這邊範例訂的規則是如果X==Y，則選擇排前面的X，這裡選擇A1作為頭，保留B1。
前一次選擇A1，比較A的第二位的數字A2和B的第一位的數字B1，選出較小的。
A2>B1，選擇B1。
將B1連接至A1的後面，兩組珠串會變成
頭: 1->1->3->4, 保留: 2->4
A1 B1 B2 B3 A2 A3前一次選擇B1，保留A2，則這一輪要比較B2和A2。
B2>A2，選擇A2。
將A2接到B1後面，兩組珠串會變成
頭: 1->1->2->4, 保留: 3->4
A1 B1 A2 A3 B2 B3依序重複步驟2~4，直到有一邊沒有數字可以比較。
(A3 < B2)
頭: 1->1->2->3->4, 保留: 4
A1 B1 A2 B2 B3 A3
因為(B3 == A3)，按照1.的規則選擇B3由於B3已經串接在合併後的珠串上，不需要更動，接下來繼續比較B3的下一個位子和保留下來的A3。
B3的下一個位置沒有珠子了，因此查看保留下來的珠子那邊。
保留下來的珠子還有A4，因此把A4串接到B3後面。
最後會珠串變成
頭: 1->1->2->3->4->4, 保留: 無
A1 B1 A2 B2 B3 A3完成合併。
迭代 Iteration
public class Solution {
public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
//邊緣案例 Edge case
if(list1==null) return list2;
if(list2==null) return list1;
//
//選擇要回傳的整理過的第一的節點
ListNode head = new ListNode();
if(list1.val<=list2.val){
head = list1;
list1 = list1.next;
}else{
head = list2;
list2 = list2.next;
}
//串接剩下的節點
ListNode curr = new ListNode();
curr = head;
while(list1!=null && list2!=null){
if(list1.val<=list2.val){
curr.next = list1;
list1=list1.next;
}else{
curr.next = list2;
list2=list2.next;
}
curr=curr.next;
}
//補上剩餘的節點
if(list1!=null) curr.next = list1;
else if (list2!=null) curr.next = list2;
return head;
}
}
複雜度分析：
- 時間複雜度：總共會有(m+n)個節點，最差的情況下是每個節點都需要比較過一次，因此時間複雜度會是O(m+n)。
- 空間複雜度：沒有使用到任何會動態增加使用空間的資料結構，因此空間複雜度為O(1)。
遞迴 Recursion
因為節點的數量最多只有100個，使用遞迴不會造成堆疊溢位(Stack Overflow)，因此這一題也可以使用遞迴的方式來解題。
遞迴的方式在概念上跟迭代是一樣的，與迭代不同的是，每個函式只做一次比較的處理，剩下的則交給下一個呼叫的函式。
public class Solution {
public ListNode MergeTwoLists(ListNode list1, ListNode list2) {
//邊緣案例 Edge case
if(list1==null) return list2;
if(list2==null) return list1;
//
//進行比較，選出較小的作為當前的頭，將下一輪的比較交給下一個呼叫的函式
ListNode tmp;
if(list1.val<list2.val){
tmp = list1.next;
list1.next = MergeTwoLists(tmp,list2);
return list1;
}else{
tmp = list2.next;
list2.next = MergeTwoLists(list1,tmp);
return list2;
}
return null;
}
}
複雜度分析：
- 時間複雜度：和迭代解法相同，最差的情況下每個節點都需要比較過一次，因此時間複雜度為O(m+n)。
- 空間複雜度：空間複雜度為單一函式所占用的空間，而遞迴在單一函式上雖然為O(1)，但是需要等到節點完成比較才能結束，所以最差的情況下會需要比較(m+n)次，因此空間複雜度會是O(m+n)。
學習重點
- 迭代與遞迴的應用。
- 鏈結串列的特性。