Reversing a Linked List

Reversing a linked list is a common and important operation that involves changing the direction of the links between nodes so that the list order is reversed.

We’ll focus on reversing a singly linked list, since it is the most instructive case.

Problem Statement

Given a singly linked list:

Head
 ↓
[1] → [2] → [3] → null

After reversal:

Head
 ↓
[3] → [2] → [1] → null

The goal is to reverse the list in-place, without allocating a new list.

Key Idea

To reverse a singly linked list, we need to:

1. Traverse the list
2. Reverse the direction of each next pointer
3. Update the head to point to the new first node

This is done by tracking three pointers:

• prev - the previous node
• current - the current node
• next - the next node (temporarily stored)

Step-by-Step Explanation

Starting state:

prev = null
current = head

At each step:

1. Save current.next in next
2. Point current.next to prev
3. Move prev and current forward

After the loop finishes:

• prev becomes the new head

Iterative Algorithm

prev = null
current = head

while current != null:
    next = current.next
    current.next = prev
    prev = current
    current = next

head = prev

Rust Implementation (Iterative)

This implementation reverses the list in-place.

// This method extends the existing SinglyLinkedList implementation.
// See the "Singly Linked List" section for the full Node and list definitions.

impl<T> SinglyLinkedList<T> {
    pub fn reverse(&mut self) {
        let mut prev: Option<Box<Node<T>>> = None;
        let mut current = self.head.take();

        while let Some(mut node) = current {
            let next = node.next.take();
            node.next = prev;
            prev = Some(node);
            current = next;
        }

        self.head = prev;
    }
}

Example Usage

fn main() {
    let mut list = SinglyLinkedList::new();

    list.push_back(1);
    list.push_back(2);
    list.push_back(3);

    println!("Before: {:?}", list.traverse()); // [1, 2, 3]

    list.reverse();

    println!("After: {:?}", list.traverse()); // [3, 2, 1]
}

Time and Space Complexity

Time Complexity

Each node is visited exactly once.

Space Complexity

Recursive Reversal (Conceptual)

Reversal can also be done recursively, but it:

• Uses additional stack space
• Is harder to reason about
• Offers no performance advantage

For clarity and efficiency, the iterative approach is preferred.

Common Mistakes

• Losing the reference to the next node
• Forgetting to update the head
• Modifying pointers in the wrong order

Carefully managing the next pointer avoids these issues.

Summary

• Reversing a linked list requires pointer manipulation
• Iterative solution is clean and efficient
• Runs in linear time and constant space
• A foundational problem for mastering linked lists

Rust - Reversing a Linked List