Python如何实现单链表逆序_基于指针变换的迭代实现技巧-Python教程-PHP中文网

不能直接改节点值逆序单链表，因题目要求原地逆序、仅调整指针；改值会丢失不可序列化对象语义或节点状态，且默认须满足o(n)时间、o(1)空间复杂度。

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

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

很多初学者看到“逆序”，第一反应是遍历一遍把所有 val 提出来，reverse() 之后再塞回去。这确实能输出正确结果，但违反了题干隐含要求：**原地逆序、仅调整指针**。真实面试或工程中，链表可能存着不可序列化对象（比如文件句柄、锁对象），或者节点本身有额外状态（如 visited 标志位），改值会丢失语义甚至引发 bug。

关键判断：只要题目明确说“反转链表”且没提“复制”“重建”，默认必须用指针操作，时间复杂度 O(n)，空间复杂度 O(1)。

三指针迭代的核心逻辑和变量命名陷阱

核心是维护三个指针：prev（已处理部分的头）、curr（当前要处理的节点）、next_temp（暂存 curr.next，防止断链）。最容易出错的是顺序写反或漏掉暂存：

错误写法：curr.next = prev; curr = curr.next → 此时 curr 已变成 prev，彻底丢失后续链
正确顺序必须是：next_temp = curr.next → curr.next = prev → prev = curr → curr = next_temp
别用 next 做变量名！Python 内置函数叫 next()，覆盖后可能在调试时引发意外行为

示例片段：

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，返回该节点本身。强行加 if not head or not head.next: return head 属于冗余代码，反而增加理解负担。

Li Python Sec Check

Python 安全规范检查工具：基于 CloudBase 规范、腾讯安全指南，LLM 智能分析（默认禁用，优先本地执行）

下载

真正要注意的是：函数返回值永远是新的头节点（即原链表尾），调用方必须用新返回值重新赋值，比如 head = reverse_list(head)，否则仍拿着旧头指针，看起来像没变。

递归解法为什么不适合长链表

虽然递归写法更简洁（先递归到底，回退时翻转指针），但 Python 默认递归深度限制约 1000 层。一旦链表长度超过这个数（比如读取日志生成的链表），直接抛 RecursionError: maximum recursion depth exceeded。而迭代法无此限制，且避免了函数调用开销和栈帧内存占用。

如果硬要用递归，必须手动调高限制：sys.setrecursionlimit(10000)，但这治标不治本——栈空间仍是线性增长，极端情况仍可能爆栈。生产环境强烈建议迭代实现。

指针变换看似简单，但每一步的暂存、赋值顺序、返回值绑定，任何一个环节松动，整条链就断了。实际调试时，拿纸画三个节点走一遍流程，比盯着代码猜要快得多。