How to Reverse a Linked List Iteratively: A Step-by-Step Guide

The question is a classic. It appears in coding interviews so often that it’s almost a rite of passage. Mastering how to reverse a linked list iteratively is a must for any developer.

It tests your understanding of pointers, node manipulation, and fundamental algorithms. This guide will break down the solution into simple, digestible steps. You will learn the logic and walk away with clear code you can use.

Let’s conquer this interview staple together.

Understanding the Problem and The Strategy

A singly linked list is a chain of nodes. Each node contains data and a next pointer to the following node. The goal is to reverse the direction of these next pointers.

The iterative approach is efficient. It uses a constant amount of extra space, making it an O(1) space solution. The time complexity is O(n) as we traverse the list once.

We will use three pointers:

• prev: Tracks the previous node, which will become the new next.
• curr: Points to the current node we are processing.
• next_temp: Temporarily stores the next node before we break the link.

This trio will march down the list, flipping pointers as they go.

Visualizing the Process

Imagine the list: 1 -> 2 -> 3 -> 4 -> None
We want: 4 -> 3 -> 2 -> 1 -> None

Here’s what happens step-by-step:

1. Initialize prev = None and curr = head (node 1).
2. Save next_temp = curr.next (node 2).
3. Flip the pointer: curr.next = prev (node 1 now points to None).
4. Move forward: prev = curr (prev is now node 1).
5. curr = next_temp (curr is now node 2).
6. Repeat until curr is None. prev will be the new head.

Python Implementation

First, we define a simple Node class to build our list.

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

def reverse_linked_list(head):
    prev = None
    curr = head

    while curr is not None:
        next_temp = curr.next  # Store next node
        curr.next = prev       # Reverse the pointer
        prev = curr            # Move prev forward
        curr = next_temp       # Move curr forward

    return prev  # prev is the new head

# Let's test it!
# Build a list: 1 -> 2 -> 3 -> None
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)

print("Original list:")
current = head
while current:
    print(current.data, end=" -> ")
    current = current.next
print("None")

# Reverse the list
new_head = reverse_linked_list(head)

print("Reversed list:")
current = new_head
while current:
    print(current.data, end=" -> ")
    current = current.next
print("None")

Output:
text
Original list:
1 -> 2 -> 3 -> None
Reversed list:
3 -> 2 -> 1 -> None

Java Implementation

The logic is identical, just with Java syntax.

class Node {
    int data;
    Node next;
    Node(int data) { this.data = data; }
}

public class LinkedList {
    public static Node reverseIteratively(Node head) {
        Node prev = null;
        Node curr = head;
        Node nextTemp = null;

        while (curr != null) {
            nextTemp = curr.next; // Store next node
            curr.next = prev;     // Reverse the pointer
            prev = curr;          // Move prev forward
            curr = nextTemp;      // Move curr forward
        }
        return prev; // New head
    }

    // Helper function to print the list
    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            System.out.print(curr.data + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        // Build list: 1 -> 2 -> 3 -> null
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);

        System.out.println("Original list:");
        printList(head);

        head = reverseIteratively(head);

        System.out.println("Reversed list:");
        printList(head);
    }
}

Why This Solution Works

The algorithm is elegant because it does the reversal in place. It doesn’t create a new list. It simply re-wires the pointers of the existing nodes.

The key is the temporary variable next_temp. It remembers the rest of the list before we break the curr.next link. Without it, we would lose our way.

Practice and Mastery

Now you know how to reverse a linked list iteratively. The next step is to practice. Draw the steps on a whiteboard. Code it from memory. Explain it to a friend.

This deep understanding will make you confident and ready to tackle any interview question that comes your way. You’ve got this.

Here are a few related topics that might help you:
How to Implement Graph in Python: A Clear and Engaging Guide
How to Solve Two Sum Problem: The Ultimate Guide