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

1. 引言

合并两个排序链表是一种常见的链表操作，通常在编程中会遇到。PHP作为一种流行的服务器端编程语言，也提供了各种方法来处理链表操作。本文将介绍一种使用PHP实现合并两个排序链表的方法。

2. 算法概述

要合并两个排序链表，我们可以使用迭代的方式逐个比较两个链表的节点，并将较小的节点添加到新的链表中，直到其中一个链表为空。然后将剩余的链表直接连接到新的链表末尾。最后返回新链表的头节点。

2.1 步骤

创建一个新的链表

初始化三个指针：指向第一个链表的指针（记为p），指向第二个链表的指针（记为q），指向新链表的指针（记为dummy）

判断p和q是否为空，如果其中一个为空，则将另一个非空链表连接到新链表的末尾

比较p和q的节点值，将较小的节点添加到新链表的末尾，然后将指向该节点的指针向前移动一步

重复步骤4，直到p或q为空

将剩余非空链表连接到新链表的末尾

返回新链表的头节点

3. PHP代码实现

下面是使用PHP实现合并两个排序链表的代码：

class ListNode {
    public $val;
    public $next;
    function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
function mergeTwoLists($l1, $l2) {
    $dummy = new ListNode();
    $cur = $dummy;
    while ($l1 != null && $l2 != null) {
        if ($l1->val < $l2->val) {
            $cur->next = $l1;
            $l1 = $l1->next;
        } else {
            $cur->next = $l2;
            $l2 = $l2->next;
        }
        $cur = $cur->next;
    }
    if ($l1 != null) {
        $cur->next = $l1;
    }
    if ($l2 != null) {
        $cur->next = $l2;
    }
    return $dummy->next;
}
// 测试
$l1 = new ListNode(1);
$l1->next = new ListNode(2);
$l1->next->next = new ListNode(4);
$l2 = new ListNode(1);
$l2->next = new ListNode(3);
$l2->next->next = new ListNode(4);
$result = mergeTwoLists($l1, $l2);
while ($result != null) {
    echo $result->val . " ";
    $result = $result->next;
}

4. 实际运行

上述代码中，我们创建了两个排序链表（$l1和$l2），并将它们传递给mergeTwoLists函数来合并。运行上述代码将输出合并后的排序链表的节点值（1 1 2 3 4 4）。

5. 总结

本文介绍了一种使用PHP实现合并两个排序链表的方法。该方法采用迭代的方式逐个比较两个链表的节点，并根据节点值的大小将节点添加到新链表中。最后返回新链表的头节点。通过这种方法，我们可以在PHP中高效地合并排序链表。