【Instagram】 / 【巴哈姆特小屋】 / 【Vocus方格子】 / 【Medium】
喜歡的話就按個愛心或贊助ㄅ。
Question and Hints
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.Return the head of the merged linked list.
Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
- The number of nodes in both lists is in the range [0, 50].
- 100 <= Node.val <= 100
- Both list1 and list2 are sorted in non-decreasing order.
First Solution
💡 題目上方的註解是在提示你所使用的程式語言，它的Node結構長怎樣，
所以不用取消註解，不然反而會顯示 NoSuchMethodError
回到解題，這個題目我有點印象，是對LinkedList進行MergeSort。
不過有點久沒寫就忘記了，而且我也沒有用Java寫過。
我最初的想法是，用4個指標，L1、L2不斷向後搜尋，當作陣列搜尋進度。
H1、H2則當作合併時的參考點。
如果L1的值大於L2，L2就繼續往後找。
如果L1的值小於或等於L2，就要開始進行合併，合併的步驟如下：
- 將L1指標向右移，此時L1表示下一個要搜尋的值，H1表示當下要進行合併的值
- H1指向L2，進行合併
- H2指向H1，表示陣列的頭
- H1指標移向L1，做為下一次合併的參考點。
不過這遇到了一些問題，
包含H2參考點仍然會越來越後面，導致最後無法回到陣列的頭，
以及Java沒有指標，而是用Node物件去進行操作的方式讓我有點混亂，
所以很可惜，第一次沒有解出來。
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// empty condition.
if(list1 == null && list2 == null)
return list1;
if(list1 == null)
return list2;
if(list2 == null)
return list1;
// Deal with link problem.
ListNode headL1 = new ListNode();
headL1 = list1;
ListNode headL2 = new ListNode();
headL2 = list2;
while(list1 != null || list2 != null){
if(list1.val <= list2.val){
list1 = list1.next;
headL1.next = list2;
headL2 = headL1;
headL1 = list1;
}
else if(list1.val > list2.val){
list2 = list2.next;
}
}
return headL2;
}
}
⏰ Runtime: ?? ms (?? %)
📦 Memory: ?? MB (?? %)
Upgrade Solution
recursive.
💡 遞迴，神奇的遞迴，OMG。
其實不用特別處理陣列為空的狀況，
此範例是合併在list1，所以兩個都空，回傳哪一個都可以，
list1為空，回傳list2的值，
而無論是list2為空，還是要回傳整理好的陣列，
都是回傳list1。
這個遞迴的運作方式，畫成圖表是長這樣：
用遞迴的方式，讓函式本身從每一輪都挑出比較小的那個值，最後遞迴結束後再反向回傳，就能得到由小到大的回傳結果。
神技。Orz
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1!=null && list2!=null){
if(list1.val < list2.val){
list1.next = mergeTwoLists(list1.next,list2);
return list1;
}
else{
list2.next = mergeTwoLists(list1,list2.next);
return list2;
}
}
if(list1==null)
return list2;
return list1;
}
}
⏰ Runtime: 0 ms (100 %)
📦 Memory: 41.8 MB (86.38 %)
Upgrade Solution 2
4 Nodes, like first solution.
💡 這個做法就解決了前面「陣列的頭跑掉」的問題，
而它不是合併在list1或list2，
而是用了一個新陣列prehead依大小吞食兩個陣列。
- 這邊用prehead作為固定不動，永遠指在最前面的標頭，用cur作為向後追蹤的參考點。
- 吞食的方式是一個一個吃，只要list1的值比較小，就將list1放進陣列，list2的值比較小，就將list2放進陣列，看是放進哪一個陣列的值，該陣列的指標就向後移一格，同時cur每吃掉一個值就往後移一格。
- 當一個陣列空了以後，檢查兩個陣列還有沒有值，有就接在cur的後面。
- 最後回傳固定在陣列頭的prehead。
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode cur = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 == null ? l2 : l1;
return prehead.next;
}
}
⏰ Runtime: 0 ms (100 %)
📦 Memory: 42.6 MB (20.37 %)
