前言:遙想當年
Linked List 同樣也是大學時期的回憶(大約大一下)，遙想當年學習過程也是相當艱辛，但後來沒也怎麼使用到 Linked List，但由於 Linked List 又是資料結構中相當重要的一課，因此，我認為 Linked List 相當適合作為我練習過程的一個重要題目。
我相信過了這麼久，即使是我沒怎麼使用到的東西，但我當初也學的算相當有成就感，我相信我應該也可以順利解決吧 !
應該吧 (?
題目
有兩個排序過的 Linked List list1 、 list2 ，合併它們變成一個 Linked List(需排序)，並返回合併後的 Lined List 的 head
// 題目預先定義之結構
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/解題過程
先嘗試喚醒陳舊( 7~8年前 )的記憶，用模糊的印象先嘗試寫出來，反正應該也不會一次就做出來吧
我一開始的想法是以 list1 為主要的 Linked List，讓 list2 每個 node 來併入 list1 ，然後我開始思考我到底要使用遞迴還是迴圈，考慮了一段時間後，後來選擇使用遞迴的方式來處理 list2 剩餘節點，使用迴圈去判斷 Node 要併入 list1 的哪裡，因為我發現這種方式到最後只需回傳 list1 就可以了
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
// list 2 合併到 list 1
if(list2 === null) {
return list1;
} else if (list1 === null) {
return list2;
}
// 取得 list2 的第一個(popout)
const popout: ListNode = new ListNode(list2.val);
list2 = list2.next;
let preNode: ListNode | null = null;
let curNode: ListNode | null = list1;
while(curNode !== null) {
if(popout.val > curNode.val) {
preNode = curNode;
curNode = curNode.next;
} else {
popout.next = curNode;
if(preNode === null) {
// 第一個情況
preNode = popout
} else {
preNode.next = popout;
}
break;
}
}
return mergeTwoLists(preNode, list2);
};
// Input
list1 = [1,2,4]
list2 = [1,3,4]
// Result
[3,4,4]
// Expected
[1,1,2,3,4,4]結果如同一開始所想的非常奇怪，但我發現到先不論如何接上各自的 node，光是 const popout: ListNode = new ListNode(list2.val); 這段應該就蠻奇怪的，即使用新建 node 的方式成功解決，我覺得這個方式也不是這個題目要的方式，使用 Linked List 就是應該希望省一點儲存空間，否則就用陣列就好了
因此我我決定換個方式，不要再新增 node
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
// list 2 合併到 list 1
if(list2 === null) {
return list1;
} else if (list1 === null) {
return list2;
}
let preNode: ListNode | null = null;
let curNode: ListNode | null = list1;
while(curNode !== null) {
if(list2.val > curNode.val) {
preNode = curNode;
curNode = curNode.next;
} else {
list2.next = curNode;
if(preNode === null) {
// 第一個的情況
preNode = list2;
} else {
preNode.next = list2;
}
break;
}
}
return mergeTwoLists(preNode, list2);
};
// Input
list1 = [1,2,4]
list2 = [1,3,4]
// Result
if(list2 === null) {
^
RangeError: Maximum call stack size exceeded
Line 3: Char 5 in solution.ts (mergeTwoLists)
Line 29: Char 12 in solution.ts (mergeTwoLists)
Line 29: Char 12 in solution.ts (mergeTwoLists)
Line 29: Char 12 in solution.ts (mergeTwoLists)
Line 29: Char 12 in solution.ts (mergeTwoLists)
Line 29: Char 12 in solution.ts (mergeTwoLists)
Line 29: Char 12 in solution.ts (mergeTwoLists)
Line 29: Char 12 in solution.ts (mergeTwoLists)我發現用遞迴的話，傳入 preNode根本不是整個 list 的起頭
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
// list 2 合併到 list 1
if(list2 === null) {
return list1;
} else if (list1 === null) {
return list2;
}
let preNode: ListNode | null = null;
let curNode: ListNode | null = list1;
let processNode: ListNode | null = list2;
while(curNode !== null) {
if(processNode.val <= curNode.val) {
list2 = list2.next;
processNode.next = curNode;
if(preNode === null) {
// 第一個的情況
list1 = processNode;
} else {
preNode.next = processNode;
}
break;
}
preNode = curNode;
curNode = curNode.next;
}
return mergeTwoLists(list1, list2);
};
// Input
list1 = [1]
list2 = [2]
// Result
if(list2 === null) {
^
RangeError: Maximum call stack size exceeded
Line 15: Char 5 in solution.ts (mergeTwoLists)
Line 44: Char 12 in solution.ts (mergeTwoLists)
Line 44: Char 12 in solution.ts (mergeTwoLists)
Line 44: Char 12 in solution.ts (mergeTwoLists)
Line 44: Char 12 in solution.ts (mergeTwoLists)
Line 44: Char 12 in solution.ts (mergeTwoLists)
Line 44: Char 12 in solution.ts (mergeTwoLists)
Line 44: Char 12 in solution.ts (mergeTwoLists)原本以為成功了，提交後發現這個 Test Case ( list1 = [1], list2 = [2] )居然報錯了…
我發現到如果是這樣的話，會使第一次 if(processNode.val <= curNode.val) 沒有跑到，導致 curNode 變成 null 跳出迴圈
那是不是只要多考慮到 else if(curNode.next === null) 就好了?
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
// list 2 合併到 list 1
if(list2 === null) {
return list1;
} else if (list1 === null) {
return list2;
}
let preNode: ListNode | null = null;
let curNode: ListNode | null = list1;
let processNode: ListNode | null = list2;
while(curNode !== null) {
if(processNode.val <= curNode.val) {
list2 = list2.next;
processNode.next = curNode;
if(preNode === null) {
// 第一個的情況
list1 = processNode;
} else {
preNode.next = processNode;
}
break;
} else if(curNode.next === null) {
list2 = list2.next;
curNode.next = processNode;
break;
}
preNode = curNode;
curNode = curNode.next;
}
return mergeTwoLists(list1, list2);
};
// Input
// list1 = [-9,3]
// list2 = [5,7]
// Result
Error - Found cycle in the ListNode
又失敗了，看來我想的太美了
我覺得我可能需要換個思路試試看，我感覺如果多一個 nextNode 來存放下個 node 會不會更順暢
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
// list 2 合併到 list 1
if(list2 === null) {
return list1;
} else if (list1 === null) {
return list2;
}
let preNode: ListNode | null = null;
let curNode: ListNode | null = list1;
let nextNode: ListNode | null = curNode.next;
let processNode: ListNode | null = list2;
while(curNode !== null) {
if(processNode.val <= curNode.val) {
list2 = list2.next;
processNode.next = curNode;
if(preNode === null) {
// 第一個的情況
list1 = processNode;
} else {
preNode.next = processNode;
}
break;
} else {
if(nextNode === null) {
// 最後一個
curNode.next = processNode;
break;
}
}
preNode = curNode;
curNode = curNode.next;
nextNode = curNode.next;
}
return mergeTwoLists(list1, list2);
};
// Result
Time Limit Exceeded感覺差了臨門一腳
重新在腦海裡跑過一遍發現到，如果 nextNode === null 是不是代表著 list1 已經到最後面了？那這樣子我只要將 curNode.next = processNode 接上去後將 list2 變成 null 就可以結束了
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
// list 2 合併到 list 1
if(list2 === null) {
return list1;
} else if (list1 === null) {
return list2;
}
let preNode: ListNode | null = null;
let curNode: ListNode | null = list1;
let nextNode: ListNode | null = curNode.next;
let processNode: ListNode | null = list2;
while(curNode !== null) {
if(processNode.val <= curNode.val) {
list2 = list2.next;
processNode.next = curNode;
if(preNode === null) {
// 第一個的情況
list1 = processNode;
} else {
preNode.next = processNode;
}
break;
} else {
if(nextNode === null) {
// 最後一個
curNode.next = processNode;
list2 = null; // -- 關鍵 --
break;
}
}
preNode = curNode;
curNode = curNode.next;
nextNode = curNode.next;
}
return mergeTwoLists(list1, list2);
};果然跟我想的一樣，接上去後將 list2 變成 null傳入下個遞迴，然後下個遞迴執行到 if(list2 === null)就會回傳 list1
結果
我覺得整體來說不是很好，這個 code 感覺很凌亂，應該還好更好的作法，來參考看看大神的作法
/*
* Author: sergeyleschev
* <https://leetcode.com/problems/merge-two-sorted-lists/solutions/1890572/100-fastest-typescript-solution>
*/
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
if (l1 === null) { return l2 }
if (l2 === null) { return l1 }
if (l1.val < l2.val)
{ l1.next = mergeTwoLists(l1.next, l2); return l1 }
else { l2.next = mergeTwoLists(l1, l2.next); return l2 }
}沒想到這樣就好了…
心得
這次的問題算是讓我重新回憶起 Linked List 的內容，雖說當初學習這段很有心得，但其實課程過後我幾乎就沒有再實作過了，後來再看到也抱持著「應該很簡單吧」、「Linked List 不就那樣嗎、的想法直到後來，後來在畢業前後有嘗試想要刷題練習，但發現到我其實有很多知識都忘了，也很多東西只大概懂理論，但根本時做不出來，所以這次的這個 Merge List 問題應該也能很好的來測試我的能力。
嘗試做後才深刻發現到 Linked List 就是我大概只懂理論，但根本實作不出來的東西。經過了幾次的嘗試努力後，每次都更接近答案一步，直到最後終於成功解出，這一刻，我感覺到當初學習 Linked List 的成就感。然而，我覺得我的 code 長得很醜，感覺給別人看，無法很快地理解我的思路與解法，所以我決定去看別人的 solution，發現到大神的 solution 非常短，相形之下我的 code 簡直雜亂無章，唯一讓我感到欣慰的是大神也有用到遞迴。
經過這次的練習還有觀摩後，我覺得對我來說除了學到大神的解法，更重要的是提醒我一個觀念，不管如何總要先嘗試做出一個版本( 即使跟xx一樣 )，再來觀摩解答或是最佳解，這樣所能感受到的想法會更深刻。
