网站导航内链建设,创意设计包装,枣庄seo外包,wordpress编辑器分段目录 题目描述#xff1a;142. 环形链表 II#xff08;中等#xff09;题目接口解题思路代码 PS: 题目描述#xff1a;142. 环形链表 II#xff08;中等#xff09;
给定一个链表的头节点 head #xff0c;返回链表开始入环的第一个节点。 如果链表无环#xff0c;则返… 目录 题目描述142. 环形链表 II中等题目接口解题思路代码 PS: 题目描述142. 环形链表 II中等
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。 不允许修改 链表。
LeetCode做题链接LeetCode-环形链表 II
示例 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 或者链表中的一个有效索引进阶 你是否可以使用 O(1) 空间解决此题
题目接口
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {}
}解题思路
参考题解环形链表 II双指针法清晰图解 遇到这种环相遇的问题第一时间就考虑快慢指针的方法如果没接触过这类问题可以看我另一篇文章环形链表 下面思路是在你理解了判断链表中是否有环的问题的基础上来说的 思路
假设有环环的长度为b起始位置到环的起点为aslow走1步fast走2步第一相遇的时候 f 2sslow sfast f因为fast是slow的两倍嘛fast 比 slow多走了 n 个环的长度所以 f s nb 快慢指针都走过前面的a步了重合时快指针就比慢指针多走n圈上面两式相减s nbf 2nb有图可知走anb步一定是在环入口有上式可知第一次相遇时慢指针已经走了nb步我们需要再走慢指针再走a步就到环入口而快指针怎么办答案是置于head位置也是再走a步就到环入口所以可以一起走a步最终快慢指针相等的位置就是环入口位置了
具体步骤
先构建一次相遇慢指针走一步快指针走两步如果有环最终在环中相遇接着构建第二次相遇慢指针位置不变快指针位置置为head也就是起始位置然后快慢指针现在都是同时走一步直到相遇相遇的位置就是环的起始结点
代码
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if (head null) {return null;}// 快慢指针都从head开始ListNode slow head;ListNode fast head;do {if (fast null || fast.next null) {return null;}// 快慢指针的移动slow slow.next;fast fast.next.next;} while (slow ! fast); // 快慢指针相遇则退出// 将快指针置于head开头慢指针不变还是在环中fast head;// 快慢指针再次相遇就是环起始节点while (fast ! slow) {// 快慢指针的移动现在都是一格一格移动快指针不再移动两个格fast fast.next;slow slow.next;}return fast;}
}PS:
感谢您的阅读如果您觉得本篇文章对您有所帮助请给予博主一个赞喔~
