PHP实现合并两个排序链表的方法

PHP实现合并两个排序链表的方法

1. 思路

• 定义一个新的链表，用来存放合并后的元素
• 依次比较两个链表中的元素大小，较小的元素作为新链表的头节点，将其后继指向较大元素的头节点
• 重复以上步骤，直到其中一个链表为空
• 将非空链表的剩余元素依次加入到新链表的末尾

2. 代码实现

class ListNode {
    public $val = 0;
    public $next = null;
    function __construct($val) {
        $this->val = $val;
    }
}

function mergeTwoLists($l1, $l2) {
    // 定义一个新的链表，用来存放合并后的元素
    $dummy = new ListNode(0);
    $cur = $dummy;
    // 依次比较两个链表中的元素大小
    while ($l1 && $l2) {
        if ($l1->val < $l2->val) {
            $cur->next = $l1;
            $l1 = $l1->next;
        } else {
            $cur->next = $l2;
            $l2 = $l2->next;
        }
        $cur = $cur->next;
    }
    // 将非空链表的剩余元素依次加入到新链表的末尾
    if ($l1) {
        $cur->next = $l1;
    }
    if ($l2) {
        $cur->next = $l2;
    }
    // 返回合并后的链表
    return $dummy->next;
}

3. 示例说明

示例一

$l1 = new ListNode(1);
$l1->next = new ListNode(3);
$l1->next->next = new ListNode(5);

$l2 = new ListNode(2);
$l2->next = new ListNode(4);
$l2->next->next = new ListNode(6);

$mergedList = mergeTwoLists($l1, $l2);
while ($mergedList) {
    echo $mergedList->val . " ";
    $mergedList = $mergedList->next;
}
// 输出结果：1 2 3 4 5 6

示例二

$l1 = new ListNode(1);
$l1->next = new ListNode(2);
$l1->next->next = new ListNode(3);

$l2 = new ListNode(4);
$l2->next = new ListNode(5);
$l2->next->next = new ListNode(6);

$mergedList = mergeTwoLists($l1, $l2);
while ($mergedList) {
    echo $mergedList->val . " ";
    $mergedList = $mergedList->next;
}
// 输出结果：1 2 3 4 5 6

两个示例中，我们分别定义了两个链表，调用mergeTwoLists函数将两个链表合并。

第一个示例中，$l1链表的元素值为1、3、5，$l2链表的元素值为2、4、6，最终合并后的结果为1、2、3、4、5、6。

第二个示例中，$l1链表的元素值为1、2、3，$l2链表的元素值为4、5、6，最终合并后的结果同样为1、2、3、4、5、6。