网站和搜索引擎,音乐网站开发,东莞企业如何建网站,便宜做网站的公司哪家好题目描述
给定一个链表#xff0c;判断链表中是否有环
题目链接
141. 环形链表
解题思路
使用快慢指针#xff08;Floyd判圈算法#xff09;#xff1a;从链表的头部设置两个指针#xff0c;p1的步长为1#xff0c; p2的步长为2#xff0c;同时向前走#xff0c;如…题目描述
给定一个链表判断链表中是否有环
题目链接
141. 环形链表
解题思路
使用快慢指针Floyd判圈算法从链表的头部设置两个指针p1的步长为1 p2的步长为2同时向前走如果p1和p2最终能够相遇则说明链表是有环的。 检测环的基本思想是非常简单的可以类比成两个人在跑道上跑。只要有圈跑的快的那个人就一定能够追上跑得慢的那个人。 代码
public class Solution {public boolean hasCycle(ListNode head) {if (head null) {return false;} //设置快慢指针ListNode slow head, fast head.next;while(slow!nullfast!nullfast.next!null){if(slow fast){return true;}slow slow.next;fast fast.next.next;}return false;}
}扩展 求环的长度 两个人相遇的是时候一定已经在环上了然后两个人只要再次在环上接着跑再次相遇的时候也就是所谓的套圈跑的快的那个人就比跑得慢的人整整多跑了一圈所以环的长度也就出来了。 用算法来描述第一次相遇后p1和p2按照原来的步长继续向前查找并且记录下两个指针遍历过的节点个数。当两个指针再次相遇的时候遍历的节点数量差就是环的长度。 求环的起点 解决方法 把其中的一个指针重置到链表头部然后两个指针步长都为1继续向前移动相遇的位置即为环的起点。 解释 首先我们设第一次相遇的时候慢指针走过的节点个数为i 设链表头部到环的起点的长度为m, 环的长度为n相遇的位 置与起点位置距离为k。 则可以得到: i m a * n k 其中a为慢指针走的圈数。 根据快指针和慢指针的速度关系我们可以得到另一个式子: 2 * i m b * n k 其中b为快指针走的圈数。 简单处理得到: i (b - a) * n 也就是说i是圈长的整数倍。 这时将其中一个节点放到起点然后同时向前走m步时此时从头部走的指针在m位置。而从相遇位置开始走的指针应该在距离起点i m, i为圈长整数倍则该指针也应该在距离起点为m的位置即环的起点。
参考
Floyd判圈算法Floyd判圈算法Floyd判圈算法龟兔赛跑算法
