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