Linked List Reversal: Methods to Reverse a Singly Linked List, Implemented Recursively and Iteratively

I. What is a Singly Linked List?¶

Before diving in, we need to understand the basic structure of a singly linked list. A singly linked list is a common data structure composed of multiple nodes. Each node contains two parts: a data field (stores data) and a pointer field (stores the address of the next node, typically denoted as next in Python). The first node of the list is called the “head node,” and the pointer field of the last node usually points to None (indicating the end of the list).

For example, a simple singly linked list can be represented as: 1 -> 2 -> 3 -> None, where 1 is the head node, and each arrow represents the direction of the next pointer.

II. Why Reverse a Linked List?¶

Reversing a linked list is a common operation used in scenarios like:
- Requiring reverse-order output of list data (e.g., printing the list from tail to head).
- Solving algorithmic problems (e.g., checking a palindrome linked list, handling lower digits first in “add two numbers”).
- Optimizing linked list operations (e.g., making certain repeated operations easier after reversal).

III. Iterative Reversal of a Singly Linked List (Recommended for Beginners)¶

Core Idea¶

The iterative approach revolves around traversing the list and reversing the pointer direction of each node one by one. We maintain three pointers: prev (previous node), current (current node), and next (next node). By cyclically moving these pointers, we gradually reverse each node’s next pointer from pointing to the next node to pointing to the previous node.

Step-by-Step Explanation¶

1. Initialize Pointers: Set prev to None (the end of the reversed list) and current to the head node head.
2. Traverse the List: While current is not None, perform the following:
   - Save current.next (the next node) to the next variable (to avoid losing subsequent nodes after pointer reversal).
   - Reverse the next pointer of current to point to prev.
   - Move prev to current (making prev the new “previous node”).
   - Move current to next (making current the new “current node”).
3. Termination: When current is None, prev becomes the head node of the reversed list.

Example Walkthrough (1->2->3->None)¶

Let’s take the linked list 1 -> 2 -> 3 -> None and walk through the reversal step by step:

• Initial State: prev = None, current = 1, next = ?
• First Iteration:
• Save next = current.next = 2;
• Reverse current.next to prev = None (list becomes 1 -> None);
• Update prev = current = 1;
• Update current = next = 2.
• Second Iteration:
• Save next = current.next = 3;
• Reverse current.next to prev = 1 (list becomes 2 -> 1 -> None);
• Update prev = current = 2;
• Update current = next = 3.
• Third Iteration:
• Save next = current.next = None;
• Reverse current.next to prev = 2 (list becomes 3 -> 2 -> 1 -> None);
• Update prev = current = 3;
• Update current = next = None.
• Termination: current is None, so reversal is complete. The new head node is prev = 3.

Python Implementation¶

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_iterative(head):
    prev = None
    current = head
    while current is not None:
        next_node = current.next  # Save the next node
        current.next = prev       # Reverse current node's pointer
        prev = current            # Move prev forward
        current = next_node       # Move current forward
    return prev  # prev is now the new head

IV. Recursive Reversal of a Singly Linked List (Understanding Recursion)¶

Core Idea¶

The recursive approach leverages the idea of first reversing the sublist after the current node, then attaching the current node to the end of the reversed sublist. The key is decomposing the problem into smaller subproblems and clarifying the base case and recursive step.

Key Concepts¶

1. Base Case: If the list is empty (head is None) or has only one node (head.next is None), return the original head node (no reversal needed).
2. Recursive Step:
   - Recursively call reverse(head.next) to get the head node of the reversed sublist (new_head).
   - Reverse the pointer of the current node head (originally pointing to the sublist head) to point to the previous node (the end of the reversed sublist).
   - Set the next pointer of head to None (making it the new tail node).
   - Return new_head (the head of the reversed sublist).

Example Walkthrough (1->2->3->None)¶

Using the linked list 1 -> 2 -> 3 -> None, let’s trace the recursion:

• Initial Call: reverse(1)
• Recursively call reverse(2), which returns new_head = 3 (reversed sublist: 3 -> 2 -> None).
• Modify the current node 1: Set head.next.next = head (i.e., 2.next = 1).
• Set head.next = None (making 1 the new tail).
• Return new_head = 3, resulting in the reversed list: 3 -> 2 -> 1 -> None.

Python Implementation¶

def reverse_recursive(head):
    # Base case: empty list or single node
    if head is None or head.next is None:
        return head
    # Recursively reverse the sublist starting from head.next
    new_head = reverse_recursive(head.next)
    # Attach current node to the end of the reversed sublist
    head.next.next = head
    # Mark current node as the new tail
    head.next = None
    return new_head  # Return the head of the reversed sublist

V. Summary¶

Comparison of Methods¶

Key Takeaways¶

• Iterative Approach: Critical to maintain pointer order (save next first, reverse, then move pointers).
• Recursive Approach: Requires clear base cases (empty/single node) and understanding how to attach the current node to the reversed sublist.

By mastering both methods, you’ll grasp the core concepts of linked list reversal. The iterative method is ideal for beginners to understand pointer manipulation, while recursion helps solidify recursive thinking in linked list problems. Practice visualizing pointer movements to master the logic!