leetcode 141. Linked List Cycle

Seawolf

1. Given a linked list, determine if it has a cycle in it.
   
2. 
   
3. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
   
4. 
   
5. 
   
6. 
   
7. Example 1:
   
8. 
   
9. Input: head = [3,2,0,-4], pos = 1
   
10. Output: true
    
11. Explanation: There is a cycle in the linked list, where tail connects to the second node.
    
12. 
    
13. 
    
14. 
    
15. Example 2:
    
16. 
    
17. Input: head = [1,2], pos = 0
    
18. Output: true
    
19. Explanation: There is a cycle in the linked list, where tail connects to the first node.
    
20. 
    
21. 
    
22. 
    
23. Example 3:
    
24. 
    
25. Input: head = [1], pos = -1
    
26. Output: false
    
27. Explanation: There is no cycle in the linked list.
    
28. 
    
29. 
    
30. Follow up:
    
31. 
    
32. Can you solve it using O(1) (i.e. constant) memory?

复制代码

1. /**
   
2. * Definition for singly-linked list.
   
3. * class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) {
   
7. *         val = x;
   
8. *         next = null;
   
9. *     }
   
10. * }
    
11. */
    
12. public class Solution {
    
13.     public boolean hasCycle(ListNode head) {
    
14.         if(head == null || head.next == null) return false;
    
15.         ListNode slow = head;
    
16.         ListNode fast = head;
    
17.         
    
18.         slow = slow.next;
    
19.         
    
20.         if(fast.next.next != null)
    
21.             fast = fast.next.next;
    
22.         else
    
23.             return false;
    
24.         
    
25.         while(fast != slow){
    
26.             
    
27.             if(fast == null) return false;
    
28.             
    
29.             slow = slow.next;
    
30.             if(fast.next == null) return false;
    
31.             if(fast.next.next == null) return false;
    
32.             fast = fast.next.next;
    
33.         }
    
34.         
    
35.         return true;
    
36.         
    
37.     }
    
38. }

复制代码