首页 > 代码库 > leetcode------Linked List Cycle II
leetcode------Linked List Cycle II
| 标题： | Linked List Cycle II |
| 通过率 | 30% |
| 难度 | 中等 |
看升级版前还是先看下 Linked List Cycle I
看完第一个版本对于第二个版本会有一定的帮助，先了解环的结构。然后看下面的图片：
假设快慢指针交汇处为为分红圈那个，环的起始点为k，那么：
1、快指针走的路程是慢指针走的两倍。
2、慢指针到相遇点时走的路径为：x+y
3、快指针到相遇点走的路径为：x+y+z+y=x+2y+z
4、又因为1，所有有 x+y=x+2y+z
5、得出：x=z
于是我们发现了起点与重合点到循环起始点额距离是一样的。那么我们放两个指针从这两个地方开始遍历，当再次重合时便是循环开始点，具体代码如下：
1 public class Solution { 2 public ListNode detectCycle(ListNode head) { 3 if(head==null) return null; 4 if(head.next==null) return null; 5 if(head.next.next==null) return null; 6 7 ListNode slow=head; 8 ListNode fast=head; 9 10 while(fast!=null && fast.next!=null){11 slow=slow.next;12 fast=fast.next.next;13 if(fast==slow){14 slow=head;15 while(slow!=fast){16 slow=slow.next;17 fast=fast.next;18 }19 return fast;20 }21 }22 23 return null;24 25 }26 }
leetcode------Linked List Cycle II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。