相交链表

怎样从“两链 4→1→8→4→5 与 5→6→1→8→4→5 在结点 8 相交,求交点。”推导出 链表 · 长度对齐，并证明每次状态变化都不会漏掉答案？

中心结论：两指针走完各自链后切换另一链头;pA 路程 a+c+b,pB 路程 b+c+a,均等于 a+b+c,在第一个公共节点相遇。

找到 2 个链表的交叉点。

在本站主例中，两链 4→1→8→4→5 与 5→6→1→8→4→5 在结点 8 相交,求交点。

算法最终需要得到或观察：两指针在节点 8(同一对象)首次相遇;无交点则同为 nil。

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

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

1. 1建模把输入翻译成“链表指针接力”，明确答案需要观察什么。
2. 2状态只维护 指针 pA/pB、是否已切换、当前 pA==pB。
3. 3转移每一步按照 两指针走完各自链后切换另一链头;pA 路程 a+c+b,pB 路程 b+c+a,均等于 a+b+c,在第一个公共节点相遇。
4. 4收尾读取 两指针在节点 8(同一对象)首次相遇;无交点则同为 nil。，并复核边界与复杂度。

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

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：指针 pA/pB、是否已切换、当前 pA==pB。

这道题的思路其实类似链表找环。

给定的 2 个链表的长度如果一样长，都从头往后扫即可。如果不一样长，需要先“拼成”一样长。把 B 拼接到 A 后面，把 A 拼接到 B 后面。这样 2 个链表的长度都是 A + B。再依次扫描比较 2 个链表的结点是否相同。

两指针走完各自链后切换另一链头;pA 路程 a+c+b,pB 路程 b+c+a,均等于 a+b+c,在第一个公共节点相遇。

执行过程中持续维护：指针 pA/pB、是否已切换、当前 pA==pB。

正确性依赖以下不变量：相交比较节点引用,不是 val。；切换后两指针总路程均为 a+b+c,长度差被抵消。

面试时可以压缩为：pA 走 A+B,pB 走 B+A;有交点在第一个公共节点相遇,无交点同时 nil;O(m+n)/O(1)。

落到当前题，执行机制可以压缩为：两指针走完各自链后切换另一链头;pA 路程 a+c+b,pB 路程 b+c+a,均等于 a+b+c,在第一个公共节点相遇。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入两链 4→1→8→4→5 与 5→6→1→8→4→5 在结点 8 相交,求交点。 因为：两指针走完各自链后切换另一链头;pA 路程 a+c+b,pB 路程 b+c+a,均等于 a+b+c,在第一个公共节点相遇。
2. 2双指针切换链表对齐起始位置差。 因为：a+b 与 b+a 路径长度相同。
3. 3指针 A 前进同步推进直到相交。 因为：切换一次后两指针对齐尾段。
4. 4指针 B 前进同步推进直到相交。 因为：切换一次后两指针对齐尾段。
5. 5指针 A 前进同步推进直到相交。 因为：切换一次后两指针对齐尾段。
6. 6指针 B 前进同步推进直到相交。 因为：切换一次后两指针对齐尾段。
7. 7相交结点值 8返回相交结点。 因为：O(m+n) 无额外空间。
8. 8收尾与复杂度两指针在节点 8(同一对象)首次相遇;无交点则同为 nil。 因为：时间 O(m+n) · 空间 O(1)。两指针走完各自链后切换另一链头;pA 路程 a+c+b,pB 路程 b+c+a,均等于 a+b+c,在第一个公共节点相遇。

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

import (
	"fmt"

)

// ListNode define
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	//boundary check
	if headA == nil || headB == nil {
		return nil
	}

	a := headA
	b := headB

	//if a & b have different len, then we will stop the loop after second iteration
	for a != b {
		//for the end of first iteration, we just reset the pointer to the head of another linkedlist
		if a == nil {
			a = headB
		} else {
			a = a.Next
		}

		if b == nil {
			b = headA
		} else {
			b = b.Next
		}
		fmt.Printf("a = %v b = %v\n", a, b)
	}
	return a
}

func main() {
    // 1. 主例
    //    输入：mode="intersection", values=[4,1,8,4,5], valuesB=[5,6,1], skipA=2, skipB=1
    //    期望：两指针在节点 8(同一对象)首次相遇;无交点则同为 nil。
    //
    // 2. 失败 / 未命中
    //    检查：不要把 val 相等当成相交;必须 pA==pB 比较引用。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC141 环形链表；LC21 合并链表
}

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

1. 1题意两链 4→1→8→4→5 与 5→6→1→8→4→5 在结点 8 相交,求交点。
2. 2重复复制整条链表或反复寻找前驱会重复走节点；哨兵和指针重连直接维护局部关系。
3. 3优化两指针走完各自链后切换另一链头;pA 路程 a+c+b,pB 路程 b+c+a,均等于 a+b+c,在第一个公共节点相遇。
4. 4证明相交比较节点引用,不是 val。；切换后两指针总路程均为 a+b+c,长度差被抵消。
5. 5复杂度时间 O(m+n)，空间 O(1)