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; } 
