LeetCode 141. 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

　　题目给了我们一个 Linked List，让我们判断它是否循环。

　　利用快，慢指针，快指针一次走2步，慢指针一次走1步，如果循环，快慢指针一定会相遇。

Java Solution:

Runtime beats 98.15%

完成日期：06/09/2017

关键词：singly-linked list；cycle

关键点：fast, slow pointers

 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 {
14     public boolean hasCycle(ListNode head) 
15     {
16         if(head == null)
17             return false;
18         
19         ListNode slow = head;
20         ListNode fast = head;
21         
22         do
23         {
24             if(fast.next == null || fast.next.next == null) // if fast reaches to end, it doens't have a cycle
25                 return false;
26             
27             fast = fast.next.next; // fast moves 2 steps
28             slow = slow.next; // slow moves 1 step
29             
30             
31         } while(fast != slow);
32         
33         return true; // if fast catches slow, meaning it has a cycle
34     }
35 }

参考资料：N/A

LeetCode 题目列表 - LeetCode Questions List

题目来源：https://leetcode.com/