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免费学习笔记（深入）”；

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) 来临时提高限制，但这只是权宜之计。递归的本质决定了其栈空间消耗与链表长度成正比，在数据量极大或环境受限的情况下，仍然存在栈溢出的风险。因此，对于生产环境的代码，迭代实现是更稳健、更推荐的选择。

说到底，指针操作就像在钢丝上行走，每一步的暂存、赋值、移动都必须精准无误。一个环节松动，整条链就断了。如果感觉代码逻辑绕不清，最好的办法不是硬想，而是拿张纸，画出三四个节点，用笔一步步模拟指针的变换过程，往往比盯着屏幕苦思冥想要高效得多。