Python如何实现单链表逆序_基于指针变换的迭代实现技巧

为什么不能直接修改节点值来逆序单链表

许多开发者在初次遇到“链表逆序”问题时，脑海中浮现的第一个解决方案往往是：遍历链表，将所有节点的值存入数组，使用 reverse() 方法翻转数组，再将值依次填回。从输出结果看，这确实能得到一个节点“值”被逆序排列的链表。然而，这种做法从根本上误解了题目的核心考察意图——链表的原地操作与指针（引用）的重定向。

这并非理论上的苛求。在实际的软件开发中，链表节点存储的数据往往并非简单的整数或字符串，而可能是无法或不应被序列化的复杂对象，例如一个打开的文件描述符、一个活跃的数据库连接，或是一个包含内部状态（如 visited 标志）的结构体。直接替换节点值，不仅会丢失对象间的关联语义，更可能引发难以调试的运行时错误。

因此，一个关键的判断原则是：只要题目要求“反转链表”，且未明确提及“复制”或“新建”，其默认的潜台词就是要求通过调整节点间的指针指向来实现，并且必须满足 O(n) 时间复杂度和 O(1) 空间复杂度的要求。这是技术面试与工程实践中公认的评估标准。

三指针迭代法的核心逻辑与变量命名避坑指南

迭代法的精髓在于同时维护三个指针的状态：prev（指向已反转部分的头节点）、curr（当前待处理的节点）、next_temp（临时保存 curr.next，防止链表断裂）。逻辑虽简洁，但初学者常犯两个错误：操作顺序颠倒，或忘记暂存后继节点。

一个典型的错误示例如下：curr.next = prev; curr = curr.next。执行第一句后，curr.next 已指向前驱节点，此时再执行第二句，curr 便错误地跳回 prev，导致原链表后半部分彻底丢失。

正确的操作顺序必须是严丝合缝的四步，缺一不可：

1. next_temp = curr.next （预先保存后继节点，确保链路不断）
2. curr.next = prev （翻转当前节点的指针方向）
3. prev = curr （prev 指针向前移动一位）
4. curr = next_temp （curr 指针向前移动一位）

另一个容易忽略但可能导致隐蔽问题的细节是：变量命名。切勿使用 next 作为变量名！因为 next() 是 Python 的内置函数，覆盖它可能在后续调试或代码扩展时引发意外行为。使用 next_temp 或 nxt 是更安全的选择。

将上述逻辑整合，标准的 Python 实现代码如下：

立即学习“Python免费学习笔记（深入）”；

def reverse_list(head):
    prev, curr = None, head
    while curr:
        next_temp = curr.next  # 必须先保存后继节点
        curr.next = prev       # 反转指针指向
        prev = curr            # prev 指针前移
        curr = next_temp       # curr 指针前移
    return prev

空链表与单节点链表是否需要特殊处理

一个常见的疑虑是：代码是否需要为边界情况（空链表或仅含一个节点）编写额外的 if 判断？答案是：完全不需要。

仔细审视循环条件 while curr:。若传入的 head 为 None（空链表），则初始 curr 即为 None，循环不会执行，函数直接返回初始值 prev（即 None），结果正确。若链表仅有一个节点，循环会执行一次，翻转后 curr 变为 None，函数返回的 prev 正是该唯一节点，同样正确。

强行添加 if not head or not head.next: return head 这类判断，属于冗余代码，不仅增加复杂度，还可能让代码阅读者产生不必要的困惑。真正需要强调的是另一个易错点：函数的返回值是反转后链表的新头节点。调用方必须使用返回值重新赋值，例如 head = reverse_list(head)。若仍持有旧的 head 指针，会发现它指向原链表的尾节点（即逆序后的最后一个节点），从而产生链表“未变化”或“变短”的错觉。

递归解法为何不适用于长链表反转

必须承认，递归写法在形式上极为优雅：先递归至链表末端，再在回溯过程中逐层翻转指针。代码简洁，逻辑直观。然而，它存在一个致命缺陷：递归深度限制。

Python 默认的递归深度约为1000层。这意味着，一旦链表长度超过此限制（例如由大规模日志数据动态生成的链表），程序将直接抛出 RecursionError。相比之下，迭代法无此限制，其空间复杂度为常数级，且避免了函数调用的额外开销。

当然，可通过 sys.setrecursionlimit(10000) 临时提高限制，但这仅是权宜之计。递归的本质决定了其栈空间消耗与链表长度成正比，在数据量极大或运行环境受限的场景下，仍存在栈溢出风险。因此，对于生产环境的代码，迭代实现是更稳健、更推荐的选择。

归根结底，指针操作如同在钢丝上行走，每一步的暂存、赋值与移动都必须精确无误。若感觉逻辑缠绕不清，最佳方法并非空想，而是用纸笔画出三四个节点，逐步模拟指针的变换过程，这往往比盯着代码苦思冥想更为高效。