☆打卡算法☆LeetCode 160. 相交链表 算法解析
☆打卡算法☆LeetCode 160. 相交链表 算法解析
恬静的小魔龙
发布于 2022-08-07 10:41:20
发布于 2022-08-07 10:41:20
一、题目
1、算法题目
“给定两个链表的头节点，找出并返回两个单链表相交的起始节点。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
image.png
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
- intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
- listA - 第一个链表
- listB - 第二个链表
- skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
- skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。
image.png
示例 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 个节点。示例 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 个节点。二、解题
1、思路分析
判断两个链表是否相交，可以使用哈希表存储链表节点。
首先，遍历链表A，将链表中的每个节点存到哈希表中。
然后遍历链表B，判断链表B中节点是否存在哈希表中。
存在就返回该节点，如果链表B所有节点都不在哈希表中，则返回null。
2、代码实现
代码参考：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode temp = headA;
while (temp != null) {
visited.add(temp);
temp = temp.next;
}
temp = headB;
while (temp != null) {
if (visited.contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
}
}
image.png
3、时间复杂度
时间复杂度：O(m+n)
其中m喝n分别是链表A和链表B的长度，需要遍历两个链表一次。
空间复杂度：O(m)
其中m是链表A的长度，需要用哈希表存储链表A中的全部节点。
三、总结
如果两个链表相交，那么相交点之后的长度是相同的。
我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。
这个位置只能是较短链表的头结点位置。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-06-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录