Given a linked list, determine if it has a cycle in it.

Example

Given -21->10->4->5, tail connects to node index 1, return true.

分析：

方法一：使用HashSet保存每一个节点。

1 /** 2  * Definition for ListNode. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int val) { 7  *         this.val = val; 8  *         this.next = null; 9  *     }10  * }11  */ 12 public class Solution {13     /**14      * @param head: The first node of linked list.15      * @return: True if it has a cycle, or false16      */17     public boolean hasCycle(ListNode head) {  18         if (head == null) return false;19         HashSet
       
         set = new HashSet
        
         ();20         while (head != null) {21             if (set.contains(head)) {22                 return true;23             }24             set.add(head);25             head = head.next;26         }27         return false;28     }29 }
        
       

方法二：

设置两个指针指向单链表的head, 然后开始遍历，第一个指针走一步，第二个指针走两步，如果没有环，它们会直接走到底，如果有环，这两个指针一定会相遇。

1 public class Solution { 2     public boolean hasCycle(ListNode head) {   3         if (head == null) return false; 4         ListNode slow = head; 5         ListNode quick = head.next; 6         while (slow != null && quick != null) { 7             if (slow == quick) return true; 8             slow = slow.next; 9             quick = quick.next;10             if (quick != null) {11                 quick = quick.next;12             }13         }14         return false;15     }16 }

Linked List Cycle II

Given a linked list, return the node where the cycle begins.

If there is no cycle, return null.

Example

Given -21->10->4->5, tail connects to node index 1，return 10。

方法一：

使用HashSet

1 /** 2  * Definition for ListNode. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int val) { 7  *         this.val = val; 8  *         this.next = null; 9  *     }10  * }11  */ 12 public class Solution {13     /**14      * @param head: The first node of linked list.15      * @return: The node where the cycle begins. 16      *           if there is no cycle, return null17      */18     public ListNode detectCycle(ListNode head) {  19         if (head == null || head.next == null) return null;20         21         Set
         
           set = new HashSet
          
           ();22         23         while (head!= null) {24             if (set.contains(head)) {25                 return head;26             } else {27                 set.add(head);28             }29             head = head.next;30          }31          return null;32     }33 }
          
         

方法二：

1 public static ListNode detectCycle(ListNode head) { 2     ListNode slow = head; 3     ListNode fast = head; 4  5     while (true) { 6         if (fast == null || fast.next == null) { 7             return null;    //遇到null了，说明不存在环 8         } 9         slow = slow.next;10         fast = fast.next.next;11         if (fast == slow) {12             break;    //第一次相遇在Z点13         }14     }15 16     slow = head;    //slow从头开始走，17     while (slow != fast) {    //二者相遇在Y点，则退出18         slow = slow.next;19         fast = fast.next;20     }21     return slow;22 }

分析：上面的代码为何能够找到环的起始位置？

假设环的长度是 m, 进入环前经历的node的个数是 k , 那么，假设经过了时间 t，那么速度为2 的指针距离起始点的位置是:  k + (2t - k) % m = k + (2t - k) - xm . 同理，速度为1的指针距离起始点的位置是 k + (t - k) % m = k + (t - k) - ym。

如果 k + (2t - k) - xm =  k  + (t - k) - ym ，可以得到 t = m (x - y)。 那么当 t 最小为m的时候，也就是说，两个指针相聚在距离环起始点 m - k 的环内。换句话说，如果把一个指针移到链表的头部，然后两个指针都以 1 的速度前进，那么它们经过 k 时间后，就可以在环的起始点相遇。

Reference: http://www.cnblogs.com/hiddenfox/p/3408931.html

转载请注明出处：cnblogs.com/beiyeqingteng/