0160. Intersection of Two Linked Lists

题目信息

题号:
  1. 相交链表

难度:

Easy

主题:

链表、双指针、路径对齐、对象身份

原题:

LeetCode 0160

重点:

将共享后缀前的长度差抵消,使两指针同步进入交点;比较节点地址而不是值,且不修改链表

题目重述

给定两条无环单链表 headA、headB,返回它们开始共享的第一个节点对象;若没有共享节点,返回 nullptr。一旦两链在某节点相交,该节点之后的整个 next 后缀都相同。相同节点值不代表相交,不得 修改原链表,进阶目标为 O(1) 额外空间。

自建示例

  • A 的独立前缀为 7 -> 2,B 的独立前缀为 9 -> 6 -> 1,二者都连接到同一对象后缀 4 -> 8:返回共享节点 4;

  • A 为 3 -> 5 -> 7,B 为另一批独立节点 1 -> 5 -> 9:虽然都有值 5,仍返回空;

  • 两个头指针本来就相同:第一个共享节点就是头;任一链为空时没有非空交点。

C++ 实现

#include <unordered_set>

class Solution {
private:
    ListNode* rememberFirstList(
        ListNode* headA,
        ListNode* headB
    ) {
        std::unordered_set<ListNode*> nodesInA;
        for (ListNode* node = headA;
             node != nullptr;
             node = node->next) {
            nodesInA.insert(node);
        }
        for (ListNode* node = headB;
             node != nullptr;
             node = node->next) {
            if (nodesInA.count(node)) {
                return node;
            }
        }
        return nullptr;
    }

    int listLength(ListNode* head) {
        int length = 0;
        while (head != nullptr) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* alignExplicitLengths(
        ListNode* headA,
        ListNode* headB
    ) {
        int lengthA = listLength(headA);
        int lengthB = listLength(headB);

        while (lengthA > lengthB) {
            headA = headA->next;
            --lengthA;
        }
        while (lengthB > lengthA) {
            headB = headB->next;
            --lengthB;
        }
        while (headA != headB) {
            headA = headA->next;
            headB = headB->next;
        }
        return headA;
    }

    ListNode* alignBySwitchingPaths(
        ListNode* headA,
        ListNode* headB
    ) {
        ListNode* first = headA;
        ListNode* second = headB;

        while (first != second) {
            first = first == nullptr ? headB : first->next;
            second = second == nullptr ? headA : second->next;
        }
        return first;
    }

public:
    ListNode* getIntersectionNode(
        ListNode* headA,
        ListNode* headB
    ) {
        return alignBySwitchingPaths(headA, headB);
    }
};

题解

相交判断的对象是节点身份

两链相交表示某一时刻两个 next 引用指向同一个 ListNode 对象,从此因为每个节点只有一个后继, 后缀全部共享。两个独立节点即使 val 相同,也不会让链的结构合并。因此所有方案都比较指针地址,不比较 节点值。

最直接的 rememberFirstList 把 A 中全部地址放入集合,再沿 B 找第一个命中地址。B 的遍历顺序保证首次 命中就是交点,时间 O(m+n);但集合保存 O(m) 个地址,没有利用共享部分一定是完整后缀的结构。

显式对齐长度为何有效

设 A、B 在交点前的独立前缀长度分别为 a、b,共享后缀长度为 c。总长度是 a+c 与 b+c,差值正好是 a-b。先让较长链的指针走过长度差,两指针到链尾的剩余距离相等,也就分别位于 长度相同的独立前缀起点;此后同步前进,若有交点会同时到达它。

alignExplicitLengths 先扫描两链求长度,再推进较长一侧,最后比较地址。若无交点,两指针会同步走到 nullptr,循环也会终止并返回空。这已经达到 O(1) 空间,但要显式计算和修改两个长度计数。

路径切换怎样自动补齐差值

让 first 先走 A,走到空后改从 B 头开始;second 先走 B,再改从 A 头开始。若有交点:

first 到交点前走:  (a + c) + b = a + b + c
second 到交点前走: (b + c) + a = a + b + c

第一段中的 c 是从交点走到链尾的共享后缀;换头后再走另一链的独立前缀。两根指针都经历一次 A 路径 和一次 B 路径,只是顺序相反,原有长度差自然抵消;到第二次进入共享后缀时,它们同时落在交点。

如果没有共享后缀,可视为 c=0。两者各走完 m+n 个节点后同时成为 nullptr;由于循环比较也把 两个空指针视为相等,正常结束,无需额外“无交点”计数器。

具体走读不同独立前缀

对 A = A1 -> A2 -> C1 -> C2、 B = B1 -> B2 -> B3 -> C1 -> C2:

指针

第一条路径

换头后的补偿

对齐位置

first

走完 A1,A2,C1,C2

再走 B1,B2,B3

C1

second

走完 B1,B2,B3,C1,C2

再走 A1,A2

C1

两个指针第一次经过 C1 的时刻可能不同,不能在那里单独停下;交换路径后消除前缀差,才会在同一轮比较 中相等。

切换发生在空指针而不是尾节点

更新写成 pointer == nullptr ? otherHead : pointer->next。指针先从尾节点走到空,下一轮才切换到另一头; 两侧遵守同一计步规则,长度等式包含完整链长。若在尾节点直接跳头,会少计空边界并使推导与实现不一致, 容易出现一轮偏差。

主解选择与复杂度

公开入口采用路径切换法:每个指针至多遍历 A、B 各一次,时间 O(m+n),只用两个指针,空间 O(1); 不写任何节点字段。显式长度对齐同样满足上界,状态更直观;路径切换把两次长度扫描和差值推进压缩进统一 游标规则。地址集合保留为从“首次重复身份”定义出发的基线,代价是线性空间。