Start learning free

LESSON 317 OF 445 · LINKED LISTS

Linked List Cycle in Rust: O(1) Space with Slow and Fast Pointers

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 9
    Ctrl + Enter to check

    RUST · LINKED LISTS

    Linked List Cycle in Rust, explained

    Problem overview

    The function has_cycle receives head, the first node of a linked list, and returns true if following the next links ever leads back to a node already visited. If the list ends, it returns false. The list can be empty, and it has at most 10,000 nodes.

    For the values [3, 2, 0, -4] where the last node links back to the node at index 1, the answer is true: the walk goes 3, 2, 0, -4, 2, 0, -4 and so on without end. For [1] with no link back, the answer is false. The position of the link back is only a way of describing the test list. The function never receives it.

    Approach: a tortoise and a hare

    An obvious solution remembers every node it has seen and reports a cycle when a node repeats. That needs O(n) memory. The follow-up asks for O(1), and Floyd's tortoise and hare gets there with two pointers.

    slow moves one node per turn and fast moves two. If the list has no cycle, fast reaches the end and the loop stops. If there is a cycle, both pointers eventually enter it and go round. Inside the cycle, each turn moves fast one node closer to slow (it gains one node per turn), so the gap between them shrinks by one each turn. It can't skip over zero, so the two pointers must land on the same node, and that is the signal.

    Nodes that can be shared

    In a cycle, two different nodes can have the same node as their next, or a pointer can come back to a node that something else already points at. A Box allows only one owner, so it can't describe that. In this lesson each node is an Rc<RefCell<ListNode>>, and Link is short for Option<Rc<RefCell<ListNode>>>. Rc is a reference-counted pointer: cloning it copies the pointer, not the node, and every clone leads to the same node. RefCell lets the node's fields be read or changed through a shared pointer, checking the rules while the program runs.

    Step by step

    1. Create the two pointers. slow is head.clone() and fast is head. Both point at the first node.
    2. Loop while fast can jump twice. Both fast.is_some() and Self::next(&fast).is_some() must hold, so that two moves are possible. next is a helper written last.
    3. Move slow one node with Self::next(&slow).
    4. Move fast two nodes with Self::next(&Self::next(&fast)).
    5. Check for a meeting. Both pointers can be None or Some, so if let (Some(s), Some(f)) = (&slow, &fast) opens a block that runs only when both stand on a node.
    6. Compare the pointers with Rc::ptr_eq(s, f) and return true if they are the same node.
    7. Return false after the loop. The loop only ends when fast reached the end of the list, so there is no cycle.
    8. Declare the helper fn next(link: &Link) -> Link.
    9. Write its body as one expression: link.as_ref().and_then(...) with a closure that returns node.borrow().next.clone().

    The solution in Rust

    impl Solution {
    fn has_cycle(head: Link) -> bool {
        let mut slow = head.clone();
        let mut fast = head;
        while fast.is_some() && Self::next(&fast).is_some() {
            slow = Self::next(&slow);
            fast = Self::next(&Self::next(&fast));
            if let (Some(s), Some(f)) = (&slow, &fast) {
                if Rc::ptr_eq(s, f) {
                    return true;
                }
            }
        }
        false
    }

    fn next(link: &Link) -> Link {
        link.as_ref().and_then(|node| node.borrow().next.clone())
    }
}

    The Rust details worth a look:

    • head.clone() copies the pointer. Cloning an Option<Rc<...>> clones the Rc inside, which only bumps a counter. Both slow and fast then lead to the same first node, and head itself is moved into fast because it isn't needed afterwards.
    • Rc::ptr_eq compares nodes, not values. Two different nodes can hold the same number, as in [1, 1, 1] with no cycle, which must give false. ptr_eq asks whether both pointers lead to the very same node.
    • as_ref() and and_then. link.as_ref() turns &Option<Rc<...>> into an Option of a reference, without moving anything. and_then returns None if the link is None, and otherwise the closure's result, which is itself an Option. So next of the end of the list is None, and next of None is also None.
    • node.borrow().next.clone(). borrow() opens the RefCell for reading. The next field is a Link, and cloning it copies a pointer, so the list isn't changed. The borrow ends when the expression ends.
    • Passing &fast lends the link. The helper takes &Link, so fast and slow stay usable after each call.
    • The if let on a tuple of references. Matching (&slow, &fast) against (Some(s), Some(f)) gives s and f as references to the Rcs, which is what ptr_eq takes.

    Complexity

    Time: O(n). Without a cycle, fast reaches the end after about n / 2 turns. With a cycle, slow enters it after at most n steps, and the gap between the pointers then closes by one per turn, which is at most the cycle's length, so the total is still linear.

    Space: O(1). The loop keeps two pointers. Cloning a link copies a pointer and doesn't allocate a node.

    Edge cases and common mistakes

    • An empty list. head is None, so the loop condition fails at once and the answer is false.
    • One node. With no link back, Self::next(&fast) is None and the loop never runs: false. If the node links to itself, the first turn puts both pointers on it and the answer is true.
    • Two nodes in a cycle. [1, 2] with the tail linked to index 0 gives true.
    • Checking only fast.is_some(). fast jumps twice, so its next node must exist too. Without that check, the second jump would walk past the end.
    • Comparing values. Equal values in different nodes are not a cycle. Compare pointers.
    • Checking for a meeting before moving. At the start both pointers are on the same node, so a check at that moment would report a cycle in every non-empty list. The check comes after both pointers have moved.

    Testing

    • [3, 2, 0, -4] with the tail linked to index 1 gives true.
    • [1, 2] with the tail linked to index 0 gives true.
    • [1] with no link back gives false.
    • [1] linked to itself gives true.
    • [1, 1, 1] with no link back gives false.
    • An empty list gives false.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free