What is the main approach to solving the Intersection of Two Linked Lists problem?

The main approaches involve using Hash Tables or the Two Pointer technique to efficiently find the intersection node, both offering O(m + n) time complexity.

Can this problem be solved in constant space?

Yes, using the Two Pointer technique, the problem can be solved in O(1) space without any extra data structures.

What happens if the two lists don't intersect?

If the two lists don't intersect, the solution will return null, which is the expected behavior when no intersection node exists.

How do the time complexities of the Hash Table and Two Pointer methods compare?

Both methods have O(m + n) time complexity, but the Hash Table method requires additional space, while the Two Pointer method is more space-efficient.

What are common pitfalls when solving the Intersection of Two Linked Lists problem?

Common pitfalls include confusing value equality with reference equality, failing to return null when there's no intersection, and misjudging space complexity when using Hash Tables.

#160

Easy

auto_awesome链表指针操作

LeetCode 题解工作台

相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。自定义评测：评测系统…

哈希表链表双指针

题目描述

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

图示两个链表在节点 c1 开始相交：

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

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

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

提示：

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

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

lightbulb

解题思路

方法一：双指针

我们使用两个指针 $a$ , $b$ 分别指向两个链表 $\textit{headA}$ , $\textit{headB}$ 。

同时遍历链表，当 $a$ 到达链表 $\textit{headA}$ 的末尾时，重新定位到链表 $\textit{headB}$ 的头节点；当 $b$ 到达链表 $\textit{headB}$ 的末尾时，重新定位到链表 $\textit{headA}$ 的头节点。

若两指针相遇，所指向的结点就是第一个公共节点。若没相遇，说明两链表无公共节点，此时两个指针都指向 null，返回其中一个即可。

时间复杂度 $O(m + n)$ ，其中 $m$ 和 $n$ 分别是链表 $\textit{headA}$ 和 $\textit{headB}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for a solution using pointer manipulation and minimal space.
question_mark
Evaluate if the candidate can optimize the solution for both time and space complexity.
question_mark
Check whether the candidate can explain the trade-offs between using hash tables and the two-pointer technique.

warning

常见陷阱

外企场景

error
Confusing value equality with reference equality: Make sure to check if the nodes are identical in memory, not just equal in value.
error
Failure to handle cases with no intersection correctly: The code should return null when no intersection is found.
error
Incorrect space complexity considerations when using Hash Tables: Candidates might underestimate memory usage when opting for hash tables.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the two linked lists have a large number of nodes? Consider optimizing the solution further.
arrow_right_alt
How would you handle the case where one list is much longer than the other? The two-pointer method accounts for this.
arrow_right_alt
Can the problem be solved with just a single traversal? It depends on the method used—hash tables or two pointers.

help

常见问题

外企场景

继续练习

#142 环形链表 II #141 环形链表 #148 排序链表