Linked List Cycle — Step-by-Step Visualization
easyLeetCode #141Hash TableLinked ListTwo Pointers
Given `head`, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the `next` pointer. Return true if there is a cycle, and false otherwise.
Algorithm Pattern
Floyd's Cycle-Finding Algorithm (Tortoise and Hare)
Key Idea
We use two pointers, `slow` and `fast`. `slow` moves one step at a time, while `fast` moves two steps at a time. If there is a cycle, the `fast` pointer will eventually 'lap' the `slow` pointer and they will meet. If `fast` reaches the end of the list (`null`), there is no cycle.
Step-by-Step Approach
- Initialize both `slow` and `fast` pointers at the `head` of the linked list.
- While `fast` and `fast.next` are not null:
- Move `slow` one step: `slow = slow.next`.
- Move `fast` two steps: `fast = fast.next.next`.
- If `slow == fast`, a cycle exists. Return `True`.
- If the loop finishes, no cycle exists. Return `False`.
Common Gotchas
- Wait, the `pos` input is just to *create* the cycle in the test case. The algorithm itself doesn't know the `pos` value.
- Always check `fast` and `fast.next` for nullity to avoid attribute errors.