PHP实现单链表反转算法详解

本文深入解析了PHP中单链表反转的核心算法，重点介绍高效稳定的三指针迭代法（通过prev、current、next三个变量安全翻转指针指向，避免断链）和简洁但需警惕栈溢出的递归实现，并附上完整可运行代码与清晰图解逻辑——无论你是初学数据结构的新手，还是需要在实际项目中快速实现链表逆序的开发者，都能从中掌握本质原理与最佳实践。

什么是单链表反转

单链表反转是指将原链表中节点的指向顺序完全颠倒，让原来的尾节点变成头节点，头节点变成尾节点。例如原链表是 1 → 2 → 3 → 4 → null，反转后变为 4 → 3 → 2 → 1 → null。这个操作不改变节点的数据，只调整指针的指向关系。

核心思路：三指针法

最常用、最直观的实现方式是使用三个变量分别记录：当前节点（current）、前一个节点（prev） 和 下一个节点（next）。遍历过程中，逐个把 current 的 next 指针指向前一个节点，再推进三个指针向前移动。

• 初始化 prev = null，current = head
• 循环中先保存 current->next（避免断链）
• 把 current->next 指向 prev
• 更新 prev = current，current = next
• 循环结束时，prev 就是新链表的头节点

PHP 实现代码（带节点定义）

以下是一个完整可运行的示例，包含 Node 类和 reverse 方法：

class ListNode {
    public $val;
    public $next;
    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}
function reverseList($head) {
$prev = null;
$current = $head;
while ($current !== null) {
$next = $current->next;  // 保存下一个节点
$current->next = $prev;   // 反转当前节点指针
$prev = $current;         // 向前推进 prev
$current = $next;         // 向前推进 current
}
return $prev;  // 新头节点
}

调用示例：
$list = new ListNode(1, new ListNode(2, new ListNode(3)));
$newHead = reverseList($list); // 返回指向 3 的节点

递归写法（理解思路用）

递归版本更简洁，但要注意 PHP 默认栈深度限制，大数据量可能触发“maximum function nesting level”错误。

function reverseListRecursive($head) {
    if ($head === null || $head->next === null) {
        return $head;
    }
    $newHead = reverseListRecursive($head->next);
    $head->next->next = $head;
    $head->next = null;
    return $newHead;
}

关键点：
- 递归到底层（最后一个节点）时返回它作为新头
- 回溯时让后续节点的 next 指向当前节点，并断开原链接

好了，本文到此结束，带大家了解了《PHP实现单链表反转算法详解》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！