vvrf / DSA.log

问题拆解

两条单链表可能在某个节点开始合并（之后完全共享同一段尾巴），要找出这个起始交点，没有则返回 null。

难点在于两条链表长度不一样，headA 和 headB 到交点的距离不同，直接齐头并进不会同时到达交点。如果先算出两边长度差，让长的那条先走几步再一起走，也能做，但要多遍历一遍算长度。

有一个更巧的对齐方式：让指针 A 走完链表 A 再接着走链表 B，指针 B 走完链表 B 再走链表 A。两者走过的总长度都是 lenA + lenB，于是会在同一时刻到达交点。

双指针换轨

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode pa = headA, pb = headB;
    while (pa != pb) {
        pa = pa != null ? pa.next : headB;
        pb = pb != null ? pb.next : headA;
    }
    return pa;
}

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

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    pa, pb := headA, headB
    for pa != pb {
        if pa != nil {
            pa = pa.Next
        } else {
            pa = headB
        }
        if pb != nil {
            pb = pb.Next
        } else {
            pb = headA
        }
    }
    return pa
}

// LeetCode 的 Rust 链表是 Option<Box<ListNode>> 独占所有权，两条链无法共享
// 尾巴，官方也没有提供本题的 Rust 签名；这里用裸指针演示同样的换轨逻辑。
pub unsafe fn get_intersection_node(
    head_a: *const ListNode,
    head_b: *const ListNode,
) -> *const ListNode {
    let (mut pa, mut pb) = (head_a, head_b);
    while pa != pb {
        pa = if pa.is_null() { head_b } else { (*pa).next };
        pb = if pb.is_null() { head_a } else { (*pb).next };
    }
    pa
}

设两条链表非公共部分长 a、b，公共部分长 c。指针 A 到交点走 a + c + b 后到达，指针 B 走 b + c + a 后到达，两者相等，所以必定在交点相遇。

如果不相交，c = 0，两个指针会在各自走完 a + b 后同时变成 None，此时 pa is pb 成立（都是 None），循环退出返回 None。这个分支正好被同一段代码覆盖，不用特判。

复杂度

指标	复杂度	原因
时间	`O(m + n)`	每个指针最多走两条链表的总长
空间	`O(1)`	只用两个指针

可以迁移的模式

两个长度不等的序列要对齐时，“各走一遍再换到对方”能凑出相同的总路程；
用 is 判断是不是同一个节点，而不是比较值；
把“不相交”设计成“同时到达 None”，就能和相交情形共用一套循环。

换轨这招的核心是构造一个两边相等的总长度，让不同步的起点自然对齐。