LeetCode#21-Merge Two Sorted Lists-合併兩個有序鏈表
- 2020 年 4 月 8 日
- 筆記
一、題目
將兩個升序鏈表合併為一個新的升序鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
示例:
輸入:1->2->4, 1->3->4 輸出:1->1->2->3->4->4
二、題解
- 解法1:遞歸
終止條件:兩條鏈表分別為 l1 和 l2,當 l1 為空或 l2 為空時結束。
如何遞歸:判斷 l1 和 l2 頭結點哪個更小,然後較小結點的 next 指針指向其餘結點的合併結果。(調用遞歸)
時間複雜度:O(n+m);空間複雜度:O(n+m)。
<?php class ListNode { public $val = 0; public $next = null; function __construct($val) { $this->val = $val; } } /** * @param ListNode $l1 * @param ListNode $l2 * @return ListNode */ function mergeTwoLists($l1, $l2) { if ($l1 == null) { return $l2; } if ($l2 == null) { return $l1; } if ($l1->val <= $l2->val) { $l1->next = mergeTwoLists($l1->next, $l2); return $l1; } if ($l2->val <= $l1->val) { $l2->next = mergeTwoLists($l2->next, $l1); return $l2; } } /** * 構建一個單鏈表(將數組轉換成鏈表) */ function createLinkedList($arr) { $linkedList = []; $current = new ListNode(array_shift($arr)); //頭節點 while (!empty($arr)) { while ($current->next != null) { $linkedList[] = $current; $current = $current->next; } $current->next = new ListNode(array_shift($arr)); } return $linkedList[0]; } $l1 = createLinkedList([1,2,4]); $l2 = createLinkedList([1,3,5]); $res = mergeTwoLists($l1, $l2); print_r($res);
得到的結果如下:
ListNode Object ( [val] => 1 [next] => ListNode Object ( [val] => 1 [next] => ListNode Object ( [val] => 2 [next] => ListNode Object ( [val] => 3 [next] => ListNode Object ( [val] => 4 [next] => ListNode Object ( [val] => 5 [next] => ) ) ) ) ) )
- 解法2:迭代
設定一個哨兵節點,用來返回合併後的鏈表,維護一個 pre
節點,調整它的 next
指針。
當 l1 當前位置的值小於等於 l2,就將 pre
節點的 next
指向 l1 的這個值,同時將 l1 指針往後移一個。反之則對 l2 做同樣的操作,直到 l1 或者 l2 指向 null。當循環終止的時候,l1 和 l2 至多有一個是非空的。
由於輸入的兩個鏈表都是有序的,所以不管哪個鏈表是非空的,只需要將剩下的那個非空鏈表接在合併鏈表的後面,並返回合併鏈表即可。
時間複雜度:O(n+m);空間複雜度:O(n+m)。
/** * @param ListNode $l1 * @param ListNode $l2 * @return ListNode */ function mergeTwoLists($l1, $l2) { // 設置一個哨兵 $node = new ListNode(null); $pre = $node; while ($l1 != null && $l2 != null) { if ($l1->val < $l2->val) { $pre->next = $l1; $l1 = $l1->next; } else { $pre->next = $l2; $l2 = $l2->next; } $pre = $pre->next; } if ($l1 == null) { $pre->next = $l2; } if ($l2 == null) { $pre->next = $l1; } return $node->next; }