长春做网站qianceyun,做景观素材有哪几个网站,如何注册小程序商家,正规网站制作公司哪里有#x1f525; 个人主页: 黑洞晓威 #x1f600;你不必等到非常厉害#xff0c;才敢开始#xff0c;你需要开始#xff0c;才会变的非常厉害 141. 环形链表
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟… 个人主页: 黑洞晓威 你不必等到非常厉害才敢开始你需要开始才会变的非常厉害 141. 环形链表
给你一个链表的头节点 head 判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
解题思路
为了判断链表中是否存在环可以使用快慢指针的方法。快指针每次向前移动两步慢指针每次向前移动一步如果链表中存在环快指针最终会追上慢指针如果不存在环快指针会到达链表尾部。
具体步骤如下
初始化快慢指针快指针每次移动两步慢指针每次移动一步。迭代遍历链表如果快指针追上了慢指针则链表存在环如果快指针到达了链表尾部则链表不存在环。
代码实现
public class Solution {public boolean hasCycle(ListNode head) {if (head null || head.next null) {return false;}ListNode slow head;ListNode fast head.next;while (slow ! fast) {if (fast null || fast.next null) {return false;}slow slow.next;fast fast.next.next;}return true;}
}142. 环形链表 II
给定一个链表的头节点 head 返回链表开始入环的第一个节点。 如果链表无环则返回 null。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。如果 pos 是 -1则在该链表中没有环。注意pos 不作为参数进行传递仅仅是为了标识链表的实际情况。
不允许修改 链表。
解题思路
要寻找环形链表的入口节点可以使用快慢指针的方法。当快慢指针相遇时让其中一个指针重新指向头节点并让两个指针以相同速度向前移动再次相遇的节点就是环的入口节点。这个方法可以证明在相遇点后再次相遇的节点就是环的入口。
具体步骤如下
使用快慢指针找到两指针相遇的节点。将其中一个指针重新指向头节点保持另一个指针在相遇点。两个指针以相同速度向前移动再次相遇的节点即为环的入口节点。
代码实现
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow head;ListNode fast head;while (fast ! null fast.next ! null) {slow slow.next;fast fast.next.next;if (slow fast) {fast head;while (slow ! fast) {slow slow.next;fast fast.next;}return slow;}}return null;}
}
