LeetCode | 相交链表

793 字

4 分钟

LeetCode | 相交链表

2026-07-31

分类：链表 / 哈希集合 / 双指针

题目#

给定两个单链表的头节点 headA 和 headB，找出两个链表相交的起始节点。如果两个链表不相交，返回 None。

这里的“相交”不是节点值相等，而是两个链表从某个节点开始共用同一段节点。

平台会根据 intersectVal、listA、listB、skipA、skipB 构造链表，但这些不是函数的直接输入。函数真正接收的是两个头节点 headA 和 headB。

要求函数返回后，两个链表仍然保持原来的结构；题目保证整个链式结构中没有环。

示例：

1
intersectVal = 8
2
listA = [4,1,8,4,5]
3
listB = [5,6,1,8,4,5]
4
skipA = 2
5
skipB = 3
6
输出：相交节点 8

其余例子略

讲解#

这道题要找的是“同一个节点对象”，不是值相同的节点。

哈希集合#

先走一遍链表 A，把 A 里面出现过的节点都放进一个集合；再走一遍链表 B，第一个已经在集合里的节点，就是相交的起始节点。

set() 是 Python 里的集合。它只关心“某个东西在不在里面”，不保存下标，也不保存对应关系。这里 visited = set() 表示创建一个空集合，visited.add(cur) 表示把当前节点放进去，cur in visited 表示判断当前节点以前是否出现过。

它和两数之和里的哈希表很像，都是利用哈希让查找平均为 O(1)。区别是：两数之和用字典保存“数字 -> 下标”，这里用集合只保存“这个节点出现过”。

长度差对齐#

先分别算出两条链表的长度 lenA 和 lenB。如果长链表比短链表多 s 个节点，就先让长链表走 s 步。这样两个指针到尾部的距离就一样了。

之后两个指针一起往后走：如果它们指向同一个节点，这个节点就是相交的起始节点；如果一直没有相同节点，最后会同时走到 None，说明不相交。

复杂度#

哈希集合法：时间复杂度 O(m + n)，空间复杂度 O(m)
长度差对齐法：时间复杂度 O(m + n)，空间复杂度 O(1)

代码#

哈希集合法#

源码#

1
class Solution:
2
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
3
        _hash =set();
4

5
        pointerA = headA
6
        while (pointerA):
7
            _hash.add(pointerA)
8
            pointerA = pointerA.next
9

10
        pointerB = headB
11
        while (pointerB):
12
            if pointerB in _hash:
13
                return pointerB
14
            pointerB = pointerB.next
15

16
        return None

长度差对齐法#

源码#

1
class Solution:
2
    def getIntersectionNode(self, headA: "ListNode", headB: "ListNode") -> "ListNode":
3
        lenA = self.getLength(headA)
4
        lenB = self.getLength(headB)
5

6
        if lenA >= lenB:
7
            long, short = headA, headB
8
        else:
9
            long, short = headB, headA
10

11
        for _ in range(abs(lenA - lenB)):
12
            long = long.next
13

14
        while long != short:
15
            long = long.next
16
            short = short.next
17

18
        return long
19

20
    def getLength(self, head: "ListNode") -> int:
21
        length = 0
22
        while head:
23
            length += 1
24
            head = head.next
25
        return length

测试#

1
class ListNode:
2
    def __init__(self, x):
3
        self.val = x
4
        self.next = None
5

6

7
sol = Solution()
8

9
common = ListNode(8)
10
common.next = ListNode(4)
11
common.next.next = ListNode(5)
12

13
headA = ListNode(4)
14
headA.next = ListNode(1)
15
headA.next.next = common
16

17
headB = ListNode(5)
18
headB.next = ListNode(6)
19
headB.next.next = ListNode(1)
20
headB.next.next.next = common
21

22
assert sol.getIntersectionNode(headA, headB) is common
23

24
headA = ListNode(2)
25
headA.next = ListNode(6)
26
headA.next.next = ListNode(4)
27

28
headB = ListNode(1)
29
headB.next = ListNode(5)
30

31
assert sol.getIntersectionNode(headA, headB) is None
32
assert sol.getIntersectionNode(None, ListNode(1)) is None
33

34
print("PASS")

参考资料#

LeetCode 原题与配图：https://leetcode.com/problems/intersection-of-two-linked-lists/
力扣官方题解：https://leetcode.cn/problems/intersection-of-two-linked-lists/solutions/811625/xiang-jiao-lian-biao-by-leetcode-solutio-a8jn/

文章分享

如果这篇文章对你有帮助，欢迎分享给更多人！

LeetCode | 相交链表

https://leetcode.cn/problems/intersection-of-two-linked-lists/

作者

平昊阳

发布于

2026-07-31

许可协议

CC BY-NC-SA 4.0

LeetCode | 二叉树的中序遍历

LeetCode | 移动零

评论区

分享你的想法，与大家交流讨论

音乐

音乐

题目#

讲解#

哈希集合#

长度差对齐#

复杂度#

代码#

哈希集合法#

源码#

长度差对齐法#

源码#

测试#

参考资料#

文章分享

评论区

音乐

文章目录