LeetCode 160. 相交链表

◎

本节目标

让两个指针分别走完两条链表，消除长度差并按节点身份找到交点。

查看 LeetCode 原题

题意与边界

给定两条无环单链表，返回它们开始共用节点的第一个位置；若没有共用节点则返回空。相交判断依据是节点身份相同，而不是节点值相等，返回后两条链表还必须保持原结构。

消除长度差

指针 first 先走链表 A，走到末尾后改走 B；second 先走 B，走到末尾后改走 A。两者都走过 A + B 长度后，起点造成的长度差被抵消：有交点时会在第一个公共节点相遇，没有交点时会同时到达空指针。

正确性依据

两条拼接路径分别是 A + B 与 B + A，总长度相同。交点之前的不同前缀只改变两指针最初的领先距离，切换链表后这段差值被补齐；公共后缀完全相同，因此第一次相等的位置就是交点。若没有公共后缀，唯一共同位置是两条路径末尾的空指针。

代码实现

C++

C++17

class Solution {
public:
    ListNode* getIntersectionNode(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;
    }
};

Python

Python 3

from typing import Optional


class Solution:
    def getIntersectionNode(
        self,
        headA: Optional[ListNode],
        headB: Optional[ListNode],
    ) -> Optional[ListNode]:
        first = headA
        second = headB
        while first is not second:
            first = headB if first is None else first.next
            second = headA if second is None else second.next
        return first

复杂度分析

• 时间复杂度：O(m + n)，每个指针至多走完两条链表。
• 空间复杂度：O(1)，只使用两个指针。

易错点

• 用节点值判断相交；值相同的两个节点仍可能是不同对象。
• 只让较短链表循环，未严格抵消长度差。
• 为了对齐长度而修改链表连接，破坏题目要求的原始结构。

模式迁移

“分别走完两段路径以消除起点差异”也可用于寻找两个路径序列的公共后缀。关键是切换后两条完整路径长度相等，并且共享部分以对象身份定义。