type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定两个单链表的头节点
headA 和 headB,返回两个单链表相交的起始节点。
图中两个链表在节点
c1 开始相交 如果两个链表不存在相交节点,返回
null 。提示:
链表必须保持其原始结构 。
题目保证整个链式结构中不存在环。
示例 1:

示例 2:

示例 3:

解法一:两次遍历
这个解法思路非常直接:
- 我们先走一遍链表 A,把 A 里的每个节点指针都丢进一个
set里;
- 然后再走一遍链表 B,每到一个节点,就看一下这个节点是不是已经在 set 里面:
- 如果在,说明这个节点就是两个链表的第一个公共节点,直接返回;
- 如果都走到底还是没遇到,那就是不相交,返回
None。
这个解法的优点就是简单,很符合直觉;缺点是要用一个额外的集合来存所有节点指针,空间是 O(m+n)。
复杂度:
- 时间:O(m + n),各走一遍;
- 空间:O(m + n)。
解法二:长度对齐
链表 A 长度为
m,链表 B 长度为 n;如果有相交,那么从交点到结尾这一段(
c)是共享的;- A 从头走到交点,走了
m - c步;
- B 从头走到交点,走了
n - c步;
如果让长的那条链先“多走几步”(如果 A 更长):
- A 先走
m - n步
- 然后 B 再出发
- 再一起同步走
- 如果有交点,就会在第一次经过该节点时相遇;
- 如果没有交点,会同时走到
None。
复杂度
- 时间:O(m + n)
- 空间:O(1)。
解法三:双指针(推荐)
把链表 A 和链表 B 想成两条不同长度的道路,如果它们有交点,那交点后面的那段道路是完全共享的。
问题在于两条链表长度不一样,直接同步往前走,会造成“有一条先走到底”。
如何让两个指针在某一个时刻到达同一个节点呢?
让它们把彼此的整条路都走一遍。 指针 P: 先走完 A,再走 B; 指针 Q:先走完 B,再走 A。
如果有交点,P和Q在经过第二次交点时,必然会在同一个时刻相遇;
如果没有交点,最后就会都停在
None上。 例子1:

P: 4 → 1 → 8 → 4 → 5 → null → 5 → 6 → 1 → 8
Q: 5 → 6 → 1 → 8 → 4 → 5 → null → 4 → 1 → 8
复杂度
- 时间:O(m + n),每个指针最多把两条链表各走一遍;
- 空间:O(1),只用了两个指针变量。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-160-相交链表
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 146] LRU 缓存
下一篇
[Leetcode 171] Excel 列名转换为数字