題型解說
這是一題難度為簡單的題目
需要設計一個方法,此方法會傳入二個已經排好序的 Linked list
將兩個 Linked list 合併成一個 Linked list 並且排好序(小到大)後回傳
範例:
list1 = [1, 2, 3, 4]、list2 = [1, 2, 3, 4],則回傳 [1, 1, 2, 2, 3, 3, 4, 4]
解題思路
我們利用一個 while 迴圈來運作,從兩個 list 中各取一個來比較
將比較小的 Node 串到要回傳的 Node 中後將該 list 的變數設為下一個 Node
用說的比較複雜,下面我們加上圖解來解釋
result 和 temp 指向同一個 Node
list1 和 list2 指向自己的 List 的開頭
接下來比較 list1 是不是小於等於 list2,如果是就將 list1 當下的 Node 移動到 result 下
然後將 list1變數 指向 list1 的下一個 Node,將 temp變數 指向最後的 Node
接下來比較 list1 是不是小於等於 list2,如果不是就將 list2 當下的 Node 移動到 result 下
然後將 list2變數 指向 list2 的下一個 Node,將 temp變數 指向最後的 Node
重複以上動作直到 list1 和 list2 都為 null 後就可以把 result 回傳了
程式碼
Java
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result = new ListNode();
ListNode temp = root;
while (l1 != null || l2 != null) {
if (l2 == null || (l1 != null && l1.val <= l2.val)) {
temp.next = l1;
l1 = l1.next;
} else if (l1 == null || (l2 != null && l2.val < l1.val)) {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
return result.next;
}
}