# Linked List Cycle

## Question

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

Challenge
Can you solve it without using extra space?


## 題解 - 快慢指標

### C++

/**
* Definition of ListNode
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: True if it has a cycle, or false
*/
bool hasCycle(ListNode *head) {
ListNode *fast = head, *slow = head;
while(fast and fast->next){
slow = slow -> next;
fast = fast -> next -> next;
if(slow == fast) return true;
}
return false;
}
};


### Java

/**
* Definition for singly-linked list.
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}

ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}


### 源碼分析

1. 異常處理，將head->next也考慮在內有助於簡化後面的代碼。
2. 慢指標初始化為head, 快指標初始化為head的下一個節點，這是快慢指標初始化的一種方法，有時會簡化邊界處理，但有時會增加麻煩，比如該題的進階版。

### 複雜度分析

1. 在無環時，快指標每次走兩步走到尾部節點，遍歷的時間複雜度為 $O(n/2)$.
2. 有環時，最壞的時間複雜度近似為 $O(n)$. 最壞情況下鏈表的頭尾相接，此時快指標恰好在慢指標前一個節點，還需 n 次快慢指標相遇。最好情況和無環相同，尾節點出現環。