首页 > 代码库 > [Leetcode][JAVA] Linked List Cycle I && II
[Leetcode][JAVA] Linked List Cycle I && II
Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
使用快慢指针，如果有循环两指针必定能相遇：
1 public boolean hasCycle(ListNode head) { 2 if(head==null) 3 return false; 4 ListNode slow = head; 5 ListNode fast = head.next; 6 while(fast!=null && fast.next!=null) 7 { 8 if(slow==fast) 9 return true;10 slow=slow.next;11 fast=fast.next.next;12 }13 return false;14 }
Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
一个快指针，一个慢指针，同点出发，如果快的走到null说明没循环，否则两指针必定相遇在一点。
然后把慢指针吊回head, 快指针与慢指针同步同速率前进，直到相遇，相遇点即为循环开始点。
原理证明：
假设头节点到循环开始节点距离为x
循环长度：y
快指针一次两步慢指针一次一步
假设相遇点为m（距离循环开始点m距离）,m必定在循环内部。
快指针移动路程: x + ky + m 慢指针移动路程: x + ty + m
x+ky+m = 2(x+ty+m)
=> ky = 2ty + x + m => (x + m) mod y = 0
所以快指针再跑x距离就能到达循环开始点。
代码：
1 public ListNode detectCycle(ListNode head) { 2 if(head==null || head.next==null) 3 return null; 4 ListNode slow=head; 5 ListNode fast=head; 6 while(true) 7 { 8 slow=slow.next; 9 if(fast==null || fast.next==null)10 return null;11 fast=fast.next.next;12 if(slow==fast)13 break;14 }15 slow=head;16 while(slow!=fast)17 {18 slow=slow.next;19 fast=fast.next;20 }21 return slow;22 }
[Leetcode][JAVA] Linked List Cycle I && II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。