EasyLinked ListTwo PointersHash Table

Linked List Cycle

1 approach, code in every language

Given the head of a singly linked list, decide whether the list contains a cycle and return true if it does, otherwise false.

A cycle exists when some node can be reached again by repeatedly following next pointers. Internally this is described by a position that the tail links back into, but that index is not given to your function; you must detect the loop purely by traversing the nodes.

Example 1

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

Output: true

The last node points back to the node at index 1 (value 2), so following next repeats forever.

Example 2

Input: head = [1], pos = -1

Output: false

A single node whose next is null has no cycle.

Constraints

The number of nodes is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 (no cycle) or a valid 0-based index into the list.

Floyd's Tortoise and Hare

Run two pointers at different speeds; a meeting proves a cycle exists.

Loading animation…

Intuition

Imagine two runners on a track, one moving one step per turn and one moving two. On a straight path with no loop the fast runner simply reaches the finish and stops. But if the path curves back into a loop, the fast runner keeps circling and eventually laps the slow runner, so at some point they occupy the same node. Detecting that collision tells us a cycle is present. If instead the fast pointer ever reaches the end of the list, there is no loop. This uses constant memory, unlike hashing every visited node.

Algorithm walkthrough

1Start both slow and fast pointers at the head.
2While fast and fast.next are non-null, advance slow by one node and fast by two nodes.
3After each move, compare the pointers; if slow equals fast they have collided inside a loop, so return true.
4If the loop terminates because fast fell off the end, the list is linear.
5Return false once fast reaches null.

Implementation

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

Time

O(n)

Space

O(1)

The pointers meet within a linear number of steps; no hash set required.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

After the pattern

Now solve one you haven't seen.

Reading a pattern isn't the same as using it. The practice set has 1,194 original problems on the same techniques, each graded in your browser.

Open the practice set Start the FDE path

1,194 problems · 15,062 graded tests · free