# 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) {
if (NULL == head || NULL == head->next) {
return false;
}

ListNode *slow = head, *fast = head->next;
while (NULL != fast && NULL != fast->next) {
fast = fast->next->next;
slow = slow->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 次快慢指针相遇。最好情况和无环相同，尾节点出现环。