同系列文章导读:【数据结构与算法】导读
所有文章均在本博客首发,其他平台同步更新
如果有更好的方法,欢迎指点,共同进步~~
有其他语言代码也可在留言区留言,谢谢
发表评论时请填写正确邮箱,以便于接收通知【推荐QQ邮箱】
环形链表II
- 时间:2022-05-19
- 题目序号:142
- 难度:中等
问题描述
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改 链表。
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
来源:力扣(LeetCode)
示例1
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例2
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例3
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
提示
- 链表中节点的数目范围在范围
[0, 104]
内 -105 <= Node.val <= 105
pos
的值为-1
或者链表中的一个有效索引
解题思路
题解部分参考自LeetCode题解和代码随想录。如有侵权,请联系进行删除~~
- 本题有两种思路:哈希表和快慢指针
- 哈希表的思想比较直观简单一些,快慢指针的话就不是很好理解
哈希表
- 在读完这个题目要求后,首先能想到的做法就是循环遍历整个链表,直到某个结点出现了第二次,也就是环的入口结点
- 对于这个思路的实现,我们可以借助于HashSet,因为HashSet中不会存储重复值
- 主要需要用到HashSet中的两个方法:
contains
和add
- 每次循环的同时首先判断HashSet中是否包含当前结点,如果已经包含了,就说明当前结点是环的入口,返回结果,结束循环
- 如果当前结点不在HashSet中,我们就把它加入到HashSet集合中,进行下一次循环
注意:这里判断当前结点是否在HashSet集合中需要对结点(地址)进行判断,而不是结点的val值
快慢指针
- 快慢指针解决本题的话,主要面临两个问题:判断是否有环、查找环的入口位置
- 这里会涉及到一些数学计算问题,不太好理解
- 具体题解大家可以去代码随想录查看,这块我有点理解不了,后面再回过头来看吧
代码实现
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode cur = head;
HashSet<ListNode> list = new HashSet<>();
while(cur != null){
if(list.contains(cur)) return cur;
else {
list.add(cur);
cur = cur.next;
}
}
return null;
}
}
总结
- 两种思路,哈希表这个方法比较容易理解
- 双指针方法分为两步:判断环和找入口,不容易理解
- 双指针法最好在纸上画一画,能更容易理解一些