Linked List Cycle

Explanation & Solution

Description

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

A cycle exists if some node in the list can be reached again by continuously following the next pointer. Internally, pos denotes the index of the node that the tail's next pointer connects to. Note that pos is not passed as a parameter — it is only used to build the linked list for testing.

Return true if there is a cycle in the linked list. Otherwise, return false.

Input:head = [3,2,0,-4], pos = 1

-4

Output: true

Explanation: There is a cycle where the tail node (-4) connects back to the node at index 1 (value 2).

Constraints

The number of nodes in the list is in the range [0, 10⁴]
-10⁵ <= Node.val <= 10⁵
pos is -1 or a valid index in the linked list

Approach

Fast and Slow Pointers pattern

1. Initialize Two Pointers

Set slow to head
Set fast to head
Both pointers start at the beginning of the linked list

2. Traverse the List

Loop while fast is not null and fast.next is not null
Move slow forward by one step: slow = slow.next
Move fast forward by two steps: fast = fast.next.next

3. Check for Cycle

After each move, compare slow and fast
If slow === fast, the two pointers have met inside the cycle
Return true — a cycle exists

4. No Cycle Found

If the loop exits (i.e., fast or fast.next is null), the list has a definite end
Return false — there is no cycle

Key Insight

This is Floyd's Cycle Detection algorithm (tortoise and hare)
If a cycle exists, the fast pointer will eventually "lap" the slow pointer and they will meet
If no cycle exists, the fast pointer will reach the end of the list

Time

O(n)in the worst case, the fast pointer traverses the list twice

Space

O(1)only two pointer variables are used, no extra data structures needed

Visualization

Input:

Linked List Traversal

—

Press play to start traversal

Slow (S)Fast (F)Both

6 steps

Solution Code

Linked List Cycle II