PHP合并有序链表方法解析

本文深入解析了PHP中合并两个有序链表的经典算法，以双指针遍历与虚拟头节点为核心技巧，在O(m+n)时间、O(1)空间内高效完成原地合并；通过清晰的逻辑拆解、带注释的实战代码及对null判断、指针推进、稳定性处理等关键细节的提醒，帮你彻底避开常见陷阱，真正掌握这一高频面试与工程实用算法的精髓。

合并两个有序链表，核心是利用它们已排序的特性，用双指针逐个比较节点值，每次取较小者接入新链表，时间复杂度 O(m+n)，空间复杂度 O(1)（不计新链表开销）。

基本思路：双指针 + 虚拟头节点

不用单独处理头节点插入逻辑，创建一个 dummy 节点作为临时头，用一个 current 指针追踪新链表尾部。遍历 l1 和 l2，比较当前节点值，将较小节点接在 current 后，并推进对应链表指针和 current 指针。

• 当其中一个链表遍历完，直接把另一个剩余部分接到 current->next
• 返回 dummy->next 即为合并后链表头
• 注意判空：任一链表为空时，可直接返回另一链表

PHP 实现代码（带注释）

假设链表节点定义如下：

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

合并函数：

function mergeTwoLists($list1, $list2) {
    $dummy = new ListNode(0);
    $current = $dummy;

    while ($list1 !== null && $list2 !== null) {
        if ($list1->val val) {
            $current->next = $list1;
            $list1 = $list1->next;
        } else {
            $current->next = $list2;
            $list2 = $list2->next;
        }
        $current = $current->next;
    }

    // 接上剩余非空链表
    $current->next = $list1 ?? $list2;

    return $dummy->next;
}

关键细节与常见陷阱

• 指针推进不能漏：每次连接后，必须更新被选中链表的指针（如 $list1 = $list1->next），否则会无限循环
• null 判断要严谨：PHP 中用 === null 比较更安全；使用空合并操作符 ?? 简洁处理剩余段
• 不新建节点，只重连指针：这是原地合并的关键，避免无谓内存分配和 val 复制
• 若要求“稳定合并”（相同值时优先保留 list1 的顺序），比较条件写成 <= 即可，已体现在示例中

测试小提示

构造两个简单有序链表，比如：
list1: 1 → 2 → 4
list2: 1 → 3 → 4
期望输出：1 → 1 → 2 → 3 → 4 → 4
调试时可加 print_r 或 var_dump 链表结构辅助验证。

以上就是《PHP合并有序链表方法解析》的详细内容，更多关于的资料请关注golang学习网公众号！