相交链表

🟢 Easy · 🏷️ 链表、双指针 · LeetCode#160

📖 题目

找出两个单链表相交的起始节点，不相交返回 None。

A:     a1 → a2 ↘
                 c1 → c2 → c3
B: b1 → b2 → b3 ↗

💡 思路

两个链表如果相交，从交点到末尾的部分完全重合，只是交点之前各自的长度不同——问题就出在这个长度差上，两个指针不能简单地同步往前走，会因为长度没对齐而永远碰不到一起。

朴素解法：先分别量出两个链表的长度，让较长的那个先走差值步，再同步往前走，相遇点就是交点。

更巧妙的解法：让两个指针都走"A接B"或"B接A"的完整路径——a 走完 A 就接着走 B，b 走完 B 就接着走 A。两人总路程都是 len(A) + len(B)，长度差就这么被抹平了，要么在交点相遇，要么同时走到 None（不相交）。

💻 代码

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

时间复杂度 O(m + n)，空间复杂度 O(1)。