Q160 链表相交

题目：给你两个单链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null。

1 我的想法

自己做出来了，但第一版踩了一个坑：提前 return nullptr 的条件写错，导致"长度不等且相交"的用例误判。

• 第一版：(flag1||flag2) && (cur1==nullptr||cur2==nullptr) → 只要有一个指针换过链，另一个一到 null 就返回 null，提前退出。
• 修正：改成 (flag1&&flag2)，两个指针都换过链之后，才可能真正没有交点。

核心：双指针各自走完自己的链后切到对方链上，把"长度差"抹平。有交点时两者会在交点相遇；没有交点时两者同时走到 null 退出。关键：提前 return 的条件必须是 flag1&&flag2，而不是 flag1||flag2。

2 简要回答

1. cur1、cur2 分别从 headA、headB 出发，同步一次走一个节点。
2. 谁走到 null 就换到另一条链的头部继续走（cur1 走完 A 切到 B，cur2 走完 B 切到 A）。
3. 相遇点就是交点；若最终都变成 null 则无交点，返回 null。

• 时间复杂度：$O(n + m)$（n、m 为两链长度，最坏各走两条链）
• 空间复杂度：$O(1)$

3 为什么"换链"能抹平长度差

两条链长度不同时，cur1、cur2 不可能在交点同步相遇。但换链之后：

• cur1 总共走完 lenA + lenB 个节点；
• cur2 同样总共走完 lenB + lenA 个节点。

两者总步数相同，于是：

• 有交点：在各自总步数到达交点时（差量被抹平）相遇。
• 无交点：两者在最后一步同时走到 null，cur1 == cur2 == nullptr，循环退出。

4 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (headA == nullptr || headB == nullptr) {
        return nullptr;
    }
    auto cur1 = headA;
    auto cur2 = headB;
    bool flag1 = 0;
    bool flag2 = 0;
    while (cur1 != cur2) {
        cur1 = cur1->next;
        cur2 = cur2->next;
        if ((flag1 && flag2) && (cur1 == nullptr || cur2 == nullptr)) {
            return nullptr;
        }
        if (cur1 == nullptr) {
            cur1 = headB;
            flag2 = 1;
        }
        if (cur2 == nullptr) {
            cur2 = headA;
            flag1 = 1;
        }
    }
    return cur1;
}

5 更简洁的等价写法

不需要 flag，利用"换链 + 循环退出条件"本身就覆盖了无交点的情况：

1
2
3
4
5
6
7
8
9

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    auto cur1 = headA;
    auto cur2 = headB;
    while (cur1 != cur2) {
        cur1 = cur1 ? cur1->next : headB;
        cur2 = cur2 ? cur2->next : headA;
    }
    return cur1;
}

• 无交点时两个指针同时变为 null，while 退出返回 null，天然正确。
• 空链也能安全处理：cur1 ? ... 不会对 null 解引用，也就不需要开头的空链判断。
• 注意：两个版本都只保证"相遇或同时为 null"，不能提前在某一个为 null 时就断定无交点。

6 易错点

• 提前 return 的条件写错是最容易犯的错：flag1||flag2 会在"长度不等且相交"时提前返回 null（先走完的那条链先到 null，但另一个指针还差几步，交点还没走到）。
• 换成 flag1&&flag2 后，两个指针都换过链，才开始判断 null；且两指针总步数相同，会同时为 null，判断是安全的。
• flag 命名容易混淆：这里 flag1 实际记录的是"cur2 换链"，flag2 记录的是"cur1 换链"，阅读时要当心。
• 直接对 null 解引用 cur1->next 会段错误：若用带 flag 的写法，务必在开头判空；用三元写法则天然安全。