Start learning free

LESSON 314 OF 442 · LINKED LISTS

Linked List Cycle in TypeScript: Floyd's Two Pointers in O(1) Space

Practice O(n) Read the full explanation

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. In the examples, pos is the index of the node that the tail's next pointer is connected to (-1 means no cycle). pos only describes how the example list is built: the tests build the cycle themselves, and pos is not passed to your function, which receives only head.

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

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed):
3 -> 2 -> 0 -> -4, and -4's next is the node 2 again.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node:
1 -> 2, and 2's next is the node 1 again.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

Constraints:

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

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

STEP 1 OF 6
    Ctrl + Enter to check

    TYPESCRIPT · LINKED LISTS

    Linked List Cycle in TypeScript, explained

    Problem overview

    The method hasCycle receives head, the first node of a singly linked list, or null for an empty list. It returns true if following the next pointers from the head can lead back to a node you have already visited, and false if the walk ends at a null.

    A cycle exists when the tail's next points at some earlier node instead of null. The position it points to, called pos in the statement, is only used to build the test lists. The method never receives it, so it must detect the cycle from the nodes alone.

    In the first example the list is 3 -> 2 -> 0 -> -4 and the tail points back to the node holding 2, so the answer is true. In the third example the single node 1 points to nothing, so the answer is false.

    Approach: a slow pointer and a fast pointer

    The obvious idea is to remember every node you visit, for example in a Set<ListNode>, and answer true the moment you see a node twice. That works in O(n) time but uses O(n) memory. The statement's follow-up asks for constant memory.

    The constant-memory idea is Floyd's tortoise and hare. Two pointers start at the head. The slow one moves one node per turn and the fast one moves two.

    • If the list has no cycle, the fast pointer reaches the end first, and the walk stops.
    • If the list has a cycle, both pointers eventually enter it and keep going round. Inside the cycle, each turn the fast pointer gains exactly one node on the slow one, so the gap between them shrinks by one every turn. A gap that shrinks by one can't skip over zero, so the pointers must land on the same node.

    Take 3 -> 2 -> 0 -> -4 with the tail pointing back to the node holding 2. Calling the nodes A (3), B (2), C (0) and D (-4), the pointers move like this:

    1. Start: slow and fast are both at A.
    2. After turn 1: slow is at B, fast is at C.
    3. After turn 2: slow is at C, fast is at B (D leads back to B).
    4. After turn 3: slow is at D, fast is at D. They meet, so the answer is true.

    Step by step

    1. Declare both pointers as ListNode | null and start them at head. The type includes null because the list can be empty.
    2. Loop while the fast pointer can jump. It moves two nodes, so both fast and fast.next must exist. Checking them in this order matters: the second check reads a field of fast, which is only safe once the first has passed.
    3. Move the slow pointer one node, to slow.next.
    4. Move the fast pointer two nodes, to fast.next.next. The loop condition already guarantees that fast.next exists.
    5. Compare the pointers. If they are the same node, the walk has gone round a cycle, so return true.
    6. Return false after the loop. The loop only ends when the fast pointer ran off the list, which can't happen in a cycle.

    The solution in TypeScript

    class Solution {
    hasCycle(head: ListNode | null): boolean {
        let slow: ListNode | null = head;
        let fast: ListNode | null = head;
        while (fast !== null && fast.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow === fast) return true;
        }
        return false;
    }
}

    The TypeScript details worth knowing:

    • === compares references for objects. slow === fast is true only when both variables hold the very same node object. Two different nodes with equal val fields are not equal: with new ListNode(1) twice, the nodes themselves compare false even though their values compare true. That is what makes the check correct for lists with repeated values.
    • The annotations are erased. ListNode | null exists only for the compiler. At run time null is just a value, and the check fast !== null is what actually protects the property reads.
    • Why slow.next is safe. The slow pointer is always behind the fast one or on the same node, so whenever the loop body runs and fast is a node, slow is a node too. The lesson's compiler settings don't complain about reading slow.next from a variable typed ListNode | null.
    • Chained reads. fast.next.next would throw a TypeError if fast.next were null. The loop condition rules that out.

    Complexity

    Time: O(n). Without a cycle, the fast pointer reaches the end after about n / 2 turns. With a cycle, the slow pointer enters the cycle after at most n turns and the gap then closes in at most one more lap of the cycle, so the total is still linear.

    Space: O(1). Two pointers are all the method stores, however long the list is.

    Edge cases and common mistakes

    • Empty list. With head = null, the loop condition is false at once and the method returns false.
    • One node. A single node whose next is null stops the loop immediately and returns false. A single node pointing at itself is a cycle: after one turn both pointers are on that node, so the method returns true.
    • Two nodes in a cycle. For [1, 2] with the tail pointing to the head, one turn puts slow on node 2 and fast back on node 1, and the second turn puts both on node 2, so the answer is true.
    • Checking only fast !== null. On a list with an even number of nodes and no cycle, the fast pointer lands on the last node, and on the next turn fast.next is null, so reading fast.next.next throws a TypeError.
    • Comparing values. slow.val === fast.val reports a cycle in [1, 1] even when there is none.
    • Testing the pointers before moving them. Both start on head, so the equality check would be true on the first pass of every list.

    Testing

    • [3, 2, 0, -4] with the tail pointing to index 1 gives true.
    • [1, 2] with the tail pointing to index 0 gives true.
    • [1] with no cycle gives false.
    • [1, 2, 3, 4] with no cycle gives false.
    • An empty list (null) gives false.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free