相交链表 图解题解

相交链表比的是节点还是值

两条单链表如果相交，由于每个节点只有一个 next，从相交点开始它们共用同一段尾巴，整体呈 Y 字形而不是 X 形。题目要找的是「开始相交的那个节点」，判断标准是节点本身——同一块内存、同一个引用，而不是值相等；两条链完全可能各自带着值相同却互不相干的节点。这个区别决定了代码里必须比较引用，比较 val 会误判。

如果两条链一样长，问题有多简单

先假设两条链长度相同：让两个指针从各自头部同步各走一步，它们距离相交点的剩余步数时刻相等，必然在相交点第一次碰头。真正的麻烦只有一个——长度不同时两个指针错了位，同步走永远差着固定几步。于是整道题归结为：怎么在不预先测长度的前提下，把这个长度差抹掉。

换头为什么恰好抹平长度差

设链 A 独有部分长 a、链 B 独有部分长 b、公共尾段长 c。让 pa 走完链 A 后接着从链 B 的头继续走，pb 走完链 B 后接着从链 A 的头继续走。pa 到达相交点的总步数是 a+c+b，pb 是 b+c+a，两个式子完全相等。

也就是说，两个指针各自把「自己的路加对方的路」走一遍之后，步调必然对齐，第一次同时踩在同一个节点上时，那里就是相交起点。长度差没有被显式计算，而是被交换路径这件事天然抵消了——这正是这个解法优雅的地方。

不相交的时候为什么不会死循环

如果两条链不相交，可以把公共段长度 c 看成零：pa 走完 a+b 步、pb 走完 b+a 步之后，两者同时越过链尾变成 null。null 等于 null，循环条件「pa 不等于 pb」不再成立，函数返回 null，恰好是不相交时的正确答案，不需要任何特判。

前提是换头时机要写对：是指针走到 null 之后才跳到对方链头，而不是走到最后一个节点就跳。跳早了两个指针的总路程不再相等，会永远错位，真的陷入死循环。

复杂度与其他解法的取舍

双指针每人最多走 m+n 步，时间 O(m+n)，只用两个指针变量，空间 O(1)。替代方案是哈希集合：先把链 A 的所有节点存进 set，再顺着链 B 找第一个出现在 set 里的节点，时间同为 O(m+n)，但要 O(m) 额外空间。也可以先各自测长、让长链先走掉差值再同步走，同样 O(1) 空间，只是要多扫一遍、代码更啰嗦——换头写法把「测长对齐」这一步整个省掉了。

Python

def getIntersectionNode(headA, headB):
    pa, pb = headA, headB
    while pa is not pb:            # 比的是节点本身,不是值
        pa = pa.next if pa else headB   # 走到尾就换到对方链头
        pb = pb.next if pb else headA
    return pa                      # 相遇即相交点(或同为 None)

C++

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB){
    ListNode *pa = headA, *pb = headB;
    while(pa != pb){                 // 比指针(节点)是否相同
        pa = pa ? pa->next : headB;   // 走到尾换对方头
        pb = pb ? pb->next : headA;
    }
    return pa;                       // 相遇即相交点(或 nullptr)
}

Java

public ListNode getIntersectionNode(ListNode headA, ListNode headB){
    ListNode pa = headA, pb = headB;
    while(pa != pb){                 // 比的是节点引用,不是 val
        pa = (pa != null) ? pa.next : headB;  // 走到尾换对方头
        pb = (pb != null) ? pb.next : headA;
    }
    return pa;                       // 相遇即相交点(或 null)
}