Start learning free

LESSON 304 OF 414 · LINKED LISTS

Reverse Linked List in Rust: O(n) Time, O(1) Space

Practice O(n) Read the full explanation

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example:

Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]


Note:

Your algorithm should run in O(n) time and use O(1) extra space.


Hints:

This problem is very similar to "Reverse String" problem, so it's natural to think of adapting that solution for Linked Lists. Unfortunately, traversing with two pointers doesn't work here because the right pointer should move to the left, and we cannot do that in a Linked List. The trick is actually in modifying the links of our Linked List to obtain its reversed version. How should we modify them?

We just have to reverse each link in the list. For example: 1 -> 2 -> 3 -> 4 should become 1 <- 2 <- 3 <- 4. And the head of the reversed list is the tail of the original one. How can we reverse these links?

One idea is to traverse the list from left to right using a variable node and convert each link node -> node.next to node.next -> node. In plain steps: start with node at the head; while node is not None, set nextNode to the node after node, make that next node point back at node, then move node forward to nextNode. But there is a problem with this algorithm. Can you find out what that is? Take some small example and run it by hand.

The problem is that the moment we reverse a link, we lose access to the next nodes. For example, if the list is 1 -> 2 -> 3. When node is 1, we reverse the link and the list becomes 1 <- 2 3. We lost the link between 2 and 3. And so at the next step node becomes 2 but node.next is 1 instead of 3. The solution is still good, but we need to implement it in such a way that this problem is fixed.

We should traverse the linked list, while using two pointers:
  • prev - the previous node
  • node - the current node
We will start with the first two nodes in the list: prev is the head and node is the node after the head. Then, for as long as node is not None, we will reverse the link prev -> node and update the two variables such that they point to the next two nodes. Can you figure out how to code this? Take the example above and figure out how you should update the pointers after each link reversal.

Start with prev at the head and node at the node after it. While node is not None:
  • save the node after node in nextNode;
  • make node point back at prev;
  • move prev to node;
  • move node to nextNode.
Don't forget to cut the old head's link to the second node, so the reversed list ends there, and return the new head.

STEP 1 OF 7
    Ctrl + Enter to check

    RUST · LINKED LISTS

    Reverse Linked List in Rust, explained

    Problem overview

    The function reverse receives the head of a singly linked list and returns the head of the same list in reverse order. In Rust a list is an Option<Box<ListNode>>: None is the empty list, and Some(box) is a node that owns the rest of the list through its next field. For [1, 2, 3, 4, 5] the result is [5, 4, 3, 2, 1].

    The statement asks for O(n) time and O(1) extra space. That means no copying the values into a vector and rebuilding: the existing nodes must be relinked, not recreated.

    Approach: move one node at a time onto a new list

    A singly linked list only points forward, so you cannot walk it from the right. Instead, reverse every link. Taking 1 -> 2 -> 3 to 1 <- 2 <- 3 is easy to say, but a naive loop that flips node.next loses the rest of the list the moment the link is flipped. The remedy is to detach the rest of the list first and keep hold of it.

    Think of two lists: the part you have not processed yet (current) and the reversed part you have built so far (prev). At each step, take the first node of current and put it in front of prev. When current runs out, prev is the answer.

    On [1, 2, 3]:

    • Start: prev = [], current = [1, 2, 3].
    • After one step: prev = [1], current = [2, 3].
    • After two steps: prev = [2, 1], current = [3].
    • After three steps: prev = [3, 2, 1], current = [].

    Every node is touched once, so the time is O(n). No new nodes are allocated, so the extra space is O(1).

    Step by step

    1. Declare prev as None. The reversed part starts empty. The annotation Option<Box<ListNode>> is needed because a bare None does not say what it could hold.
    2. Move head into current. This is a move, not a copy: from here on current owns the whole list.
    3. Loop with while let Some(mut node) = current. Each pass moves the first box out of current into node. It is mut because the loop changes its next field. When current is None the pattern fails and the loop ends.
    4. Detach the rest. node.next.take() returns the tail and leaves None behind in node.next. Assigning it to current gives the loop its next node. Because the pattern moved current out, assigning to it here simply gives it a fresh value.
    5. Reverse the link. node.next = prev makes the node own the already reversed part. This is the step that flips the direction.
    6. Make the node the new front. prev = Some(node) wraps the box back in an Option.
    7. Return prev as the last expression, with no semicolon.

    The solution in Rust

    impl Solution {
    fn reverse(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut prev: Option<Box<ListNode>> = None;
        let mut current = head;
        while let Some(mut node) = current {
            current = node.next.take();
            node.next = prev;
            prev = Some(node);
        }
        prev
    }
}

    Rust details worth knowing:

    • Ownership does the bookkeeping. A node can have only one owner. When node.next = prev runs, prev is moved into the node, and the next line gives prev a new value. At no point do two variables own the same node, which is why the code needs no unsafe and no reference counting.
    • take() replaces a value with None. Option::take swaps the option for None and hands you the old content. It is the standard way to pull a tail out of a node. Here node is an owned box, so writing current = node.next; also compiles and gives the same result; take() is the idiom that keeps working when you only hold a &mut to a node, as in the removal problems.
    • while let moves the value. Some(mut node) = current moves the box out of current. That is fine as long as current is assigned again before the next test, which the first line of the body does.
    • No semicolon on the last line. prev alone is the function's value. prev; would make the body evaluate to () and fail to compile.

    Complexity

    Time: O(n). The loop runs once per node, and each pass does a fixed number of pointer moves.

    Space: O(1). The loop keeps three variables, prev, current and node. Boxes are moved between them, never copied.

    Edge cases and common mistakes

    • Empty list. reverse(None) skips the loop and returns prev, which is None.
    • One node. [7] goes through the loop once, with node.next set to None, and comes back as [7].
    • Flipping the link before saving the tail. Setting node.next = prev before reading the old tail overwrites the only handle on the rest of the list, so the tail is dropped. Take the tail first.
    • Returning current or head. After the loop current is None and head has been moved. The answer is prev.

    Testing

    • [1, 2, 3, 4, 5] gives [5, 4, 3, 2, 1].
    • [7] gives [7].
    • [] gives [].
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free