首页 > 代码库 > LeetCode解题报告:Linked List Cycle && Linked List Cycle II
LeetCode解题报告:Linked List Cycle && Linked List Cycle 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?
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?
思路：
对于判断链表是否有环:用两个指针，一开始都指向头结点，一个是快指针，一次走两步，一个是慢指针，一次只走一步，当两个指针重合时表示存在环了。
证明：假设链表有环，环的长度为N,慢指针在起始位置，快指针在位置k（位置从0开始计数），那么快指针只要比慢指针多走经过N-k步，就可以追上慢指针了。，因为每一次快指针都比慢指针多走一步，所以一定可以在有限的步数追上慢指针。
如何求出环的起始位置，结论：当快指针和慢指针重合的时候，把一个指针重新指向头指针，两个指针现在速度一样，一次走一步，那么当两个指针值相同时，所在的指针就是环的起始位置。
可以看看这篇文章的解释，看着像我邮学长的blog：http://blog.csdn.net/sysucph/article/details/15378043
代码：
1 public class LinkedListCycle { 2 public boolean hasCycle(ListNode head) { 3 ListNode fast = head; 4 ListNode slow = head; 5 while (fast != null && (fast.next != null)) { 6 fast = fast.next.next; 7 slow = slow.next; 8 if (fast == slow) { 9 return true;10 }11 }12 return false;13 }14 15 public ListNode detectCycle(ListNode head) {16 ListNode fast = head;17 ListNode slow = head;18 boolean hasCycle = false;19 while (fast != null && (fast.next != null)) {20 fast = fast.next.next;21 slow = slow.next;22 if (fast == slow) {23 hasCycle = true;24 break;25 }26 }27 if (!hasCycle) {28 return null;29 } else {30 // find the start of the cycle31 slow = head;32 while (slow != fast) {33 slow = slow.next;34 fast = fast.next;35 }36 return fast;37 }38 }39 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。