LeetCode#21-Merge Two Sorted Lists-合并兩個有序鏈表

一、題目

將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例:

輸入: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;
}
posted @ 2020-04-08 01:21  鹿呦呦  閱讀(...)  評論(...編輯  收藏
最新chease0ldman老人