# 160. 相交链表

# 题目描述

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

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

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

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5],
     skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8。
     从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
     在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

1
2
3
4
5
6

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4],
     skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2。

1
2
3
4

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5],
     skipA = 3, skipB = 2
输出：No intersection
解释：两个链表不相交，因此返回 null。

1
2
3
4

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

**进阶：**能否设计一个时间复杂度为 O(m + n)、仅使用 O(1) 内存的解决方案？

# 思路

先明确什么叫“相交”。

两个节点的值相同，就说明相交了吗？并不是。链表中完全可以有多个值相同但地址不同的节点。

本题判断的是两个指针是否指向同一个节点，而不是节点值是否相等。

而且单链表一旦相交，交点之后的所有节点都会共用。因为一个节点只有一个 next 指针，不可能从交点之后再次分开。

# 哈希表

最直观的办法，是先遍历链表 A，把访问过的节点全部放进哈希集合，再遍历链表 B：

如果当前节点已经在集合中，它就是第一个相交节点；
如果遍历到链表末尾仍未找到，两个链表就不相交。

这种方法的时间复杂度是 O(m + n)，但需要 O(m) 的额外空间。进阶要求只使用常数空间，还能怎么做呢？

# 双指针切换链表

假设：

链表 A 在交点前有 a 个节点；
链表 B 在交点前有 b 个节点；
两个链表相交后，共有 c 个节点。

如果两个指针分别从 headA、headB 同时出发，因为 a 和 b 不一定相等，它们通常不会同时到达交点。

长度差怎么消掉？

定义两个指针 curA 和 curB：

curA 先走完链表 A，到达空节点后切换到 headB；
curB 先走完链表 B，到达空节点后切换到 headA。

这样，curA 走过的路线是：

a + c + b

curB 走过的路线是：

b + c + a

两条路线长度相同。虽然两个指针起点不同，但各自切换一次链表后，长度差被两个指针走过的不同前缀抵消了，它们会同时到达第一个相交节点。

很多录友第一次看到这个写法，会觉得“走到空节点再换条链表”有点绕。其实核心就一句话：你走我的前缀，我走你的前缀，两个人走过的总路程就一样长了。

如果两个链表不相交呢？

curA 和 curB 都走完 m + n 个节点后，会同时变成 null。此时 curA == curB，循环同样能够正常结束并返回 null，不需要额外判断。

# 模拟过程

以示例 1 为例：

A：4 → 1 ↘
          8 → 4 → 5
B：5 → 6 → 1 ↗

1
2
3

注意，两个链表中的节点 8 是同一个节点，它后面的 4 → 5 也被两个链表共用。

第 1 步：初始化两个指针。

curA 指向链表 A 的头节点 4，curB 指向链表 B 的头节点 5。因为两个链表在交点前的长度不同，直接同步移动不能保证在交点相遇。

第 2 步：走到空节点后切换链表。

curA 依次走过 A → B，curB 依次走过 B → A。两个指针都把两条链表走了一遍，只是顺序相反。

第 3 步：两个指针在节点 8 相遇。

移动 9 次后，curA 和 curB 同时指向节点 8。比较的是节点地址，所以节点 8 就是两个链表的第一个相交节点，直接返回。

# 解题代码

class Solution {
public:
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;

        while (curA != curB) {
            // 走完自己的链表后，从另一条链表的头节点继续走
            curA = (curA == nullptr) ? headB : curA->next;
            curB = (curB == nullptr) ? headA : curB->next;
        }

        // 相交时返回交点；不相交时二者同时为 nullptr
        return curA;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

循环条件为什么是 curA != curB，而不是判断两个指针都不为空？

因为指针到达 null 后还要切换到另一条链表。如果一看到 null 就结束循环，长度差还没有被消除，整个思路就走不下去了。

# 复杂度分析

时间复杂度：O(m + n)。两个指针最多各遍历两条链表一次。
空间复杂度：O(1)。只使用了两个指针。

# 其他语言

# Python3

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        cur_a = headA
        cur_b = headB

        while cur_a is not cur_b:
            # 走完自己的链表后，从另一条链表的头节点继续走
            cur_a = headB if cur_a is None else cur_a.next
            cur_b = headA if cur_b is None else cur_b.next

        return cur_a

1
2
3
4
5
6
7
8
9
10
11

# Java

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;

        while (curA != curB) {
            // 走完自己的链表后，从另一条链表的头节点继续走
            curA = (curA == null) ? headB : curA.next;
            curB = (curB == null) ? headA : curB.next;
        }

        return curA;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# Go

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    curA, curB := headA, headB

    for curA != curB {
        if curA == nil {
            curA = headB
        } else {
            curA = curA.Next
        }

        if curB == nil {
            curB = headA
        } else {
            curB = curB.Next
        }
    }

    return curA
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# JS

var getIntersectionNode = function(headA, headB) {
    let curA = headA;
    let curB = headB;

    while (curA !== curB) {
        // 走完自己的链表后，从另一条链表的头节点继续走
        curA = (curA === null) ? headB : curA.next;
        curB = (curB === null) ? headA : curB.next;
    }

    return curA;
};

1
2
3
4
5
6
7
8
9
10
11
12

# 与代码随想录联系

这道题的关键仍然是代码随想录链表章节反复强调的基本功：操作和比较的是节点指针，不是节点值。

代码随想录的链表相交使用“先计算长度差，再让长链表先走”的方法，把两个指针对齐到距离尾节点相同的位置。本文的指针切换法没有显式计算长度，但本质完全一样：都是在消除两条链表的长度差。

建议录友们把本题和19. 删除链表的倒数第 N 个结点、142. 环形链表 II放在一起练习。这三道题都没有修改链表结构，而是通过设计指针的出发位置或移动路线，让两个指针在目标节点相遇。

← 142. 环形链表 II 1. 两数之和 →

验证登录状态...