# LeetCode Linked List Cycle: Two Pointers, Reversal and Hash

## Overview

LeetCode Linked List Cycle could be solved by slow/fast pointers and reversing the linked list or by using hashing method. I compare these three methods here.

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

Can you solve it without using extra space?

## Two (slow/fast) Pointers Solution

By similar idea to find the middle node of a linked list, we maintain two pointers, the slow pointer to scan the linked list one step by one step and the fast pointer to scan the linked list two steps at time. If there is a cycle, the fast pointer will overlap the slow pointer sometime, if there is no cycle, the scanning could be ended normally once reaching to the end of the linked list. To detect such overlapping, we need the maintain the complete information about the nodes the fast pointer went through, so we keep two separate pointers for the faster scanning and if there is a cycle, the slow pointer must be overlapped with one of these two fast pointers (think about the details of the reason here). And the following code is accepted by LeetCode OJ to pass this Linked List Cycle problem:

Update: the following one might be less elegant but is useful for the follow up question to return the start node of the cycle, and the only difficulty for me to see about this algorithm is that I found it difficult to prove that the following slow/fast pointer meets at the same node in O(N) time, how and what key fact guarantee that they could meet at the same time in O(N) bound? Anyone could point me to some reference and that would highly appreciated!