反转链表：如何不丢掉后半段链表

怎样从“反转 1→2→3→4→5 为 5→4→3→2→1；核心是在改 cur.Next 前先保存 next。”推导出 链表 · 三指针反转，并证明每次状态变化都不会漏掉答案？

中心结论：每轮三拍：next=cur.Next → cur.Next=prev → prev=cur; cur=next。先保存后继再改指向，避免断链。

反转 1→2→3→4→5 为 5→4→3→2→1；核心是在改 cur.Next 前先保存 next。

在本站主例中，反转 1→2→3→4→5 为 5→4→3→2→1；核心是在改 cur.Next 前先保存 next。

算法最终需要得到或观察：头结点变为 5,整条链完全反转,后半段从未失联。

复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“链表指针接力”，明确答案需要观察什么。
2. 2状态只维护 已反转区(prev)、未处理区(cur)、临时保护(next)。
3. 3转移每一步按照 每轮三拍：next=cur.Next → cur.Next=prev → prev=cur; cur=next。先保存后继再改指向，避免断链。
4. 4收尾读取 头结点变为 5,整条链完全反转,后半段从未失联。，并复核边界与复杂度。

画清每根 next 指针改变前后的归属，再写代码。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：已反转区(prev)、未处理区(cur)、临时保护(next)。

每轮三拍：next=cur.Next → cur.Next=prev → prev=cur; cur=next。先保存后继再改指向，避免断链。

执行过程中持续维护：已反转区(prev)、未处理区(cur)、临时保护(next)。

正确性依赖以下不变量：prev 链是 cur 之前已完成反转的前缀。

面试时可以压缩为：三指针 prev/cur/next：每轮先 next=cur.Next 防丢链，再 cur.Next=prev，再 prev=cur、cur=next；cur 为空时 return prev。O(n)/O(1)。

落到当前题，执行机制可以压缩为：每轮三拍：next=cur.Next → cur.Next=prev → prev=cur; cur=next。先保存后继再改指向，避免断链。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入反转 1→2→3→4→5 为 5→4→3→2→1；核心是在改 cur.Next 前先保存 next。 因为：每轮三拍：next=cur.Next → cur.Next=prev → prev=cur; cur=next。先保存后继再改指向，避免断链。
2. 2保存 next=1,断开 cur→next先记住后继,再把当前结点指向前驱。 因为：不断开 next 会丢失后半段。
3. 3预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
4. 4三指针整体前移处理下一个结点。 因为：每次只反转一条边,O(n)。
5. 5保存 next=3,断开 cur→next先记住后继,再把当前结点指向前驱。 因为：不断开 next 会丢失后半段。
6. 6保存 next=4,断开 cur→next先记住后继,再把当前结点指向前驱。 因为：不断开 next 会丢失后半段。
7. 7保存 next=null,断开 cur→next先记住后继,再把当前结点指向前驱。 因为：不断开 next 会丢失后半段。
8. 8收尾与复杂度头结点变为 5,整条链完全反转,后半段从未失联。 因为：时间 O(n) · 空间 O(1)。每轮三拍：next=cur.Next → cur.Next=prev → prev=cur; cur=next。先保存后继再改指向，避免断链。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func reverseList(head *ListNode) *ListNode {
	var behind *ListNode
	for head != nil {
		next := head.Next
		head.Next = behind
		behind = head
		head = next
	}
	return behind
}

func main() {
    // 1. 主例
    //    输入：mode="reverse", values=[1,2,3,4,5]
    //    期望：头结点变为 5,整条链完全反转,后半段从未失联。
    //
    // 2. 失败 / 未命中
    //    检查：丢失 next 前未保存 cur.next,链会断。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC92 反转链表 II；LC25 K 个一组反转
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意反转 1→2→3→4→5 为 5→4→3→2→1；核心是在改 cur.Next 前先保存 next。
2. 2重复复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。
3. 3优化每轮三拍：next=cur.Next → cur.Next=prev → prev=cur; cur=next。先保存后继再改指向，避免断链。
4. 4证明prev 链是 cur 之前已完成反转的前缀。
5. 5复杂度时间 O(n)，空间 O(1)