How do you reverse a linked list?

How to Reverse a Linked List: A Comprehensive Guide

Linked lists are fundamental data structures in computer science. They're useful for many things, but sometimes you need to reverse one. This guide shows you how, covering both iterative and recursive methods.

What is a Linked List?

Imagine a train. Each train car is a node. Each node holds some data and a pointer (like a coupler) to the next car. A linked list is a sequence of these nodes, connected by their pointers. The last car has its pointer pointing to nothing (NULL).

Why Reverse a Linked List?

Reversing a linked list is a common task in programming. It's helpful in scenarios like implementing undo/redo functionality or reversing a stack (a LIFO data structure) efficiently.

Iterative Approach

The iterative method uses loops. It's generally more efficient than recursion. Here's how it works:

1. Three pointers: We need three pointers: prev (previous node), curr (current node), and next (next node).
2. Iteration: We iterate through the list, changing the pointers of each node to reverse the direction.
3. Update: In each iteration, curr's next pointer points to prev, prev becomes curr, and curr moves to the next node.

Python Code Example (Iterative)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def reverse_list_iterative(head):
    prev = None
    curr = head
    while curr:
        next = curr.next  # Store the next node
        curr.next = prev  # Reverse the pointer
        prev = curr       # Move prev forward
        curr = next       # Move curr forward
    return prev

Time and Space Complexity (Iterative)

Time complexity: O(n) - We visit each node once. Space complexity: O(1) - We use a constant amount of extra space.

Recursive Approach

The recursive method is elegant but can be less efficient for very large lists (due to potential stack overflow).

1. Base Case: If the list is empty or has only one node, it's already reversed.
2. Recursive Step: Reverse the rest of the list recursively. Then, make the rest of the list point back to the first node.

Python Code Example (Recursive)

def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

Time and Space Complexity (Recursive)

Time complexity: O(n). Space complexity: O(n) in the worst case (due to recursive call stack).

Comparing Iterative and Recursive

The iterative approach is generally preferred because of its better space complexity. The recursive approach is more concise but might lead to stack overflow issues for very long lists.

Real-world Applications

Reversing a linked list has practical uses:

• Undo/Redo functionality: Store actions in a linked list and reverse to undo.
• Polynomial representation: Efficiently storing and manipulating polynomials.

Conclusion

Reversing a linked list is a valuable skill for any programmer. Practice both the iterative and recursive approaches to solidify your understanding.

Try the code examples! Let us know in the comments if you have any questions.