0160. Intersection of Two Linked Lists ====================================== 题目信息 -------- :题号: 0160. 相交链表 :难度: 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++ 实现 -------- .. code-block:: cpp #include class Solution { private: ListNode* rememberFirstList( ListNode* headA, ListNode* headB ) { std::unordered_set 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 头开始。若有交点: .. code-block:: text 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``: .. list-table:: :header-rows: 1 * - 指针 - 第一条路径 - 换头后的补偿 - 对齐位置 * - ``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)``; 不写任何节点字段。显式长度对齐同样满足上界,状态更直观;路径切换把两次长度扫描和差值推进压缩进统一 游标规则。地址集合保留为从“首次重复身份”定义出发的基线,代价是线性空间。