0160. 相交链表 #
- 标签:链表、双指针
- 难度:简单
题目大意 #
描述:给定 listA
、listB
两个链表。
要求:判断两个链表是否相交,返回相交的起始点。如果不相交,则返回 None
。
说明:
listA
中节点数目为 $m$。listB
中节点数目为 $n$。- $1 \le m, n \le 3 * 10^4$。
- $1 \le Node.val \le 10^5$。
- $0 \le skipA \le m$。
- $0 \le skipB \le n$。
- 如果
listA
和listB
没有交点,intersectVal
为 $0$。 - 如果
listA
和listB
有交点,intersectVal == listA[skipA] == listB[skipB]
。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:双指针 #
如果两个链表相交,那么从相交位置开始,到结束,必有一段等长且相同的节点。假设链表 listA
的长度为 $m$、链表 listB
的长度为 $n$,他们的相交序列有 $k$ 个,则相交情况可以如下如所示:
现在问题是如何找到 $m - k$ 或者 $n - k$ 的位置。
考虑将链表 listA
的末尾拼接上链表 listB
,链表 listB
的末尾拼接上链表 listA
。
然后使用两个指针 pA
、pB
,分别从链表 listA
、链表 listB
的头节点开始遍历,如果走到共同的节点,则返回该节点。
否则走到两个链表末尾,返回 None
。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(m + n)$。
- 空间复杂度:$O(1)$。