题目描述:
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null
。
进阶:你能否设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案?
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
示例 1:
1 | 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 |
示例 2:
1 | 输入:intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1 |
示例 3:
1 | 输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 |
提示:
listA
中节点数目为m
listB
中节点数目为n
- $0 <= 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 + 1] == listB[skipB + 1]
链接:
https://leetcode-cn.com/problems/intersection-of-two-linked-lists
题目分析
首先想到最简单的方法就是使用哈希表记录一条链表的所有结点,再遍历另一条链表比对是否存在相同结点即可。这样的算法时间复杂度是 $O(m+n)$,因为需要分别遍历两条链表;而空间复杂度是 $O(m)$,也即需要保存一条链表的所有结点所构成的一个哈希表。
如何达到进阶要求中线性的时间复杂度和常数的空间复杂度呢?我们需要思考的是如何让两个指针同时到达相交的那个交点。两条链表在相交前的结点数可能是不一样的,但是相交后就是一条链表,如果我们让两个指针分别遍历两个链表,则它们走过的路程就是一样的了。
具体的算法是这样的,让两个指针分别从两个链表头部出发,每次前进一个结点,如果前进到链表末尾就换另一条链表头部开始遍历,两个指针相遇或者同时为空的时候结束遍历得到结果。我们分别对四种情况来验证这个算法的正确性:
- 两条链表有相交且相交前结点数相同。假设相交前的结点有
a
个,则两个指针前进了a
步就相遇了,得到结果。 - 两条链表有相交且相交前结点数不同。假设相交前的结点分别为
a
和b
个,由于a
和b
不相等,在第一次进入相同部分时两个指针并不会相遇,假设相同部分长度为c
,则两个指针一前一后完成了对链表的遍历(不会同时为空),这个时候两个指针分别去到了另外一条链表开始遍历,到相同结点时,第一个指针走了a+c+b
的路程,第二个指针走了b+c+a
的路程,是相等的,于是他们相遇了,我们就得到了结果。 - 两条链表没有相交且结点数相同。两个指针分别遍历了各自链表之后同时到达终点成为空指针。
- 两条链表没有相交且结点数不同。两个指针分别遍历了两条链表之后同时到达终点成为空指针。
1 | class Solution { |
时间复杂度:$O(m+n)$,其中 $m、n$ 分别是两条链表的长度。两个指针最多都只对两条链表进行一次遍历。
空间复杂度:$O(1)$。我们只需要两个指针的额外空间。