160. 相交链表 (Easy)

专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/intersection-of-two-linked-lists/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

题目数据保证整个链式结构中不存在环。

注意： 函数返回结果后，链表必须保持其原始结构。

示例：

• 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
• 输出：Intersected at ‘8’
• 解释：相交节点的值为 8（注意，相交是节点引用相同，不是值相同）

---

题目详细分析

• 数据范围： 链表节点数在 [1, 3 * 10^4] 范围内，节点值在 [1, 10^5] 范围内
• 输入特征： 两个链表可能在某个节点之后共享同一段节点（Y 形结构），也可能完全不相交
• 核心约束： 不能破坏链表结构，不能使用额外 O(n) 空间（进阶要求）
• 隐藏条件： 相交是基于节点引用（指针地址）相同而非节点值相同，所以不能用值判断
• 边界条件： 其中一个链表为空、两个链表都为空、两个链表完全相同（头节点即相交）、不相交

---

小白版直白理解

想象两条路，开始时是分开的，但走到某个点之后汇合成同一条路。就像两条河流在某个地方合并了。现在要找到那个汇合点。难点在于两条路的长度可能不一样，但我们没有一个地图看清全局。

一个巧妙的方法：两个探险家分别从两条路的起点出发，一个人走完自己的路后，换到另一条路的起点继续走；另一个人也一样。因为他们走过的总路程最终会一样长，所以一定会在汇合点碰面。

---

解题思路

思路一：双指针等路程法（推荐）

为什么这样想： 设链表 A 的不相交部分长度为 a，链表 B 的不相交部分为 b，相交部分为 c。指针 pA 走完自己的路 a+c，再走 b 到相交点；指针 pB 走完自己的路 b+c，再走 a 到相交点。两者总路程都是 a+b+c，因此必然同时到达相交点。

关键洞察： 两个指针分别从不同起点出发，通过「交换赛道」消除长度差，最终在相交点相遇。如果没有相交点，则它们会同时到达 null。

def getIntersectionNode(headA, headB):
    """双指针等路程法"""
    if not headA or not headB:
        return None
    
    pA, pB = headA, headB
    while pA != pB:
        # pA 走完了换到 headB，pB 走完了换到 headA
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA  # 相遇点或 None

思路二：哈希集合法

思路讲解： 先遍历链表 A，将所有节点引用存入哈希集合。再遍历链表 B，遇到的第一个在集合中的节点就是相交点。直观易懂，但需要额外 O(m) 空间。

def getIntersectionNode(headA, headB):
    """哈希集合法"""
    visited = set()
    cur = headA
    while cur:
        visited.add(cur)
        cur = cur.next
    
    cur = headB
    while cur:
        if cur in visited:
            return cur
        cur = cur.next
    return None

思路三：长度差法

思路讲解： 先分别计算出两个链表的长度，让较长的链表先走长度差步，然后两个指针同步前进，相遇点就是相交点。思路直接，但需要两轮遍历。

def getIntersectionNode(headA, headB):
    """长度差法"""
    def get_length(head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length
    
    lenA, lenB = get_length(headA), get_length(headB)
    # 长的先走差值步
    if lenA > lenB:
        for _ in range(lenA - lenB):
            headA = headA.next
    else:
        for _ in range(lenB - lenA):
            headB = headB.next
    
    # 同步前进找交点
    while headA != headB:
        headA = headA.next
        headB = headB.next
    return headA

---

易错点

• 值相等不等于节点相交： 相交判断的是节点引用（pA is pB），不是节点值相等（pA.val == pB.val）。两个不同节点可以有相同的值
• 空链表处理： 任一链表为空时直接返回 None
• 无相交情况： 等路程法在无相交时会同时到达 None，返回 None，不需要特殊判断
• 死循环风险： 等路程法的 while 循环条件用 pA != pB，如果链表不相交且代码写错（没有换路逻辑），会产生死循环
• 交换赛道的时机： 是 pA = pA.next if pA else headB，而不是 pA = pA.next if pA.next else headB。前者在 pA 为 None 时换路，后者会跳过最后一个节点

---

框架提炼

双指针等路程模板： 适用于判断两个链表相交或寻找相交点的问题。两个指针分别从两个链表出发，走到末尾后切换到对方链表起点，利用路程相等消除长度差。

def find_intersection(headA, headB):
    pA, pB = headA, headB
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA

这个模板的核心思想是「交换赛道消去长度差」，也可以推广到其他需要消除两个序列长度差的问题。

---

关联题目

• 141-环形链表 — 同样是快慢/双指针思想，判断链表是否有环
• 142-环形链表II — 双指针找环入口，与本题的「等路程相遇」数学原理相似