Reverse a Singly Linked List Iterative in DSA C++

Mental Model

We change the direction of each link in the list one by one until the whole list points backward.

Analogy: Imagine a line of people holding hands forward. We ask each person to turn around and hold hands with the person behind them instead, starting from the front.

head -> 1 -> 2 -> 3 -> null
          ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> null

Goal: Reverse the list so it becomes 3 -> 2 -> 1 -> null

Step 1: Initialize prev to null, curr to head (node 1)

prev = null, curr = 1 -> 2 -> 3 -> null

Why: We start with no previous node and current at the head to begin reversing links

Step 2: Save next node (2), reverse curr's pointer to prev (null), move prev to curr (1), curr to next (2)

1 -> null, prev = 1 -> null, curr = 2 -> 3 -> null

Why: We reverse the first link and move forward to continue reversing

Step 3: Save next node (3), reverse curr's pointer to prev (1), move prev to curr (2), curr to next (3)

2 -> 1 -> null, prev = 2 -> 1 -> null, curr = 3 -> null

Why: We reverse the second link and move forward

Step 4: Save next node (null), reverse curr's pointer to prev (2), move prev to curr (3), curr to next (null)

3 -> 2 -> 1 -> null, prev = 3 -> 2 -> 1 -> null, curr = null

Why: We reverse the last link; curr is now null so we stop

Result:

3 -> 2 -> 1 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

Node* reverseList(Node* head) {
    Node* prev = nullptr; // previous node starts as null
    Node* curr = head;    // current node starts at head
    while (curr != nullptr) {
        Node* nextTemp = curr->next; // save next node
        curr->next = prev;           // reverse pointer
        prev = curr;                 // move prev forward
        curr = nextTemp;             // move curr forward
    }
    return prev; // prev is new head
}

void printList(Node* head) {
    Node* curr = head;
    while (curr != nullptr) {
        cout << curr->val << " -> ";
        curr = curr->next;
    }
    cout << "null" << endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);

    cout << "Original list: ";
    printList(head);

    Node* reversed = reverseList(head);

    cout << "Reversed list: ";
    printList(reversed);

    return 0;
}

Node* prev = nullptr; // previous node starts as null Node* curr = head; // current node starts at head

initialize pointers to start reversing

while (curr != nullptr) {

loop until we reach the end of the list

Node* nextTemp = curr->next; // save next node

keep next node safe before changing pointer

curr->next = prev; // reverse pointer

reverse current node's pointer to previous node

prev = curr; // move prev forward curr = nextTemp; // move curr forward

advance prev and curr pointers to continue reversal

return prev; // prev is new head

return new head after full reversal

Output

Original list: 1 -> 2 -> 3 -> null

Reversed list: 3 -> 2 -> 1 -> null

Complexity Analysis

Time: O(n) because we visit each node once to reverse the pointers

Space: O(1) because we only use a few pointers, no extra data structures

vs Alternative: Compared to recursive reversal which uses O(n) stack space, iterative reversal is more space efficient

Edge Cases

empty list (head is null)

function returns null immediately, no reversal needed

DSA C++

while (curr != nullptr) {

single node list

pointer reversal happens but list remains same, function returns the single node

DSA C++

while (curr != nullptr) {

When to Use This Pattern

When you need to reverse the order of a singly linked list, use the iterative reversal pattern by changing pointers step-by-step.

Common Mistakes

Mistake: Not saving the next node before reversing the pointer, causing loss of the rest of the list
Fix: Always save curr->next in a temporary variable before changing curr->next

Mistake: Returning the original head instead of the new head after reversal
Fix: Return prev pointer after the loop ends, as it points to the new head

Summary

Reverses a singly linked list by changing the direction of pointers iteratively.

Use when you want to reverse the order of nodes in a singly linked list efficiently.

The key is to keep track of previous, current, and next nodes to reverse links safely.

Practice

1. What is the main purpose of the iterative method to reverse a singly linked list?

easy

A. To sort the nodes in ascending order

B. To change the direction of the links between nodes one by one

C. To delete all nodes from the list

D. To create a new linked list with the same elements

Solution

1. Step 1: Understand the linked list structure

   A singly linked list has nodes connected by pointers going one way only.

2. Step 2: Purpose of iterative reversal

   The iterative method changes each node's pointer to point backward, reversing the list.

3. Final Answer:

   To change the direction of the links between nodes one by one -> Option B

4. Quick Check:

   Reversing = Changing links direction [OK]

Hint: Think of flipping arrows between nodes one at a time [OK]

Common Mistakes:

• Confusing reversal with deletion
• Thinking it sorts the list
• Assuming it creates a new list

2. Which of the following is the correct syntax to initialize the previous pointer to NULL in C++ before starting the reversal?

easy

A. Node* prev = NULL;

B. Node prev = NULL;

C. Node prev* = 0;

D. Node prev = 0;

Solution

1. Step 1: Understand pointer initialization

   In C++, pointers are declared with * and can be set to NULL or nullptr.

2. Step 2: Correct pointer declaration

   "Node* prev = NULL;" correctly declares a pointer named prev and initializes it to NULL.

3. Final Answer:

   Node* prev = NULL; -> Option A

4. Quick Check:

   Pointer prev initialized to NULL [OK]

Hint: Use * for pointers and assign NULL or nullptr [OK]

Common Mistakes:

• Declaring pointer without *
• Assigning NULL to non-pointer variable
• Using 0 without pointer declaration

3. What will be the output linked list after running the iterative reverse function on the list: 1 -> 2 -> 3 -> null?

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. null -> 1 -> 2 -> 3

D. 2 -> 3 -> 1 -> null

Solution

1. Step 1: Trace reversal of 1 -> 2 -> 3

   Start with prev = NULL, curr = 1. Change 1's next to NULL, move prev to 1, curr to 2.

2. Step 2: Continue reversing links

   Change 2's next to 1, move prev to 2, curr to 3. Then change 3's next to 2, prev to 3, curr to NULL.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

4. Quick Check:

   Reversed list = 3 -> 2 -> 1 [OK]

Hint: Reverse pointers one by one from head to tail [OK]

Common Mistakes:

• Not updating pointers correctly
• Leaving last node pointing to old next
• Confusing original and reversed order

4. Identify the error in this iterative reversal code snippet:

Node* reverse(Node* head) {
  Node* prev = NULL;
  Node* curr = head;
  while (curr != NULL) {
    Node* next = curr->next;
    curr->next = prev;
    prev = curr;
    // Missing update of curr here
  }
  return prev;
}

medium

A. prev is not initialized to NULL

B. The function returns head instead of prev

C. next pointer is not declared

D. The pointer curr is never updated inside the loop, causing an infinite loop

Solution

1. Step 1: Check loop pointer updates

   Inside the loop, curr must move to next node to avoid infinite loop.

2. Step 2: Identify missing update

   The code misses 'curr = next;' causing curr to never change and loop forever.

3. Final Answer:

   The pointer curr is never updated inside the loop, causing an infinite loop -> Option D

4. Quick Check:

   Missing curr update = infinite loop [OK]

Hint: Always move current pointer forward inside the loop [OK]

Common Mistakes:

• Forgetting to update curr
• Returning wrong pointer
• Not initializing prev

5. Given a singly linked list with nodes containing values [10, 20, 30, 40, 50], which of the following code snippets correctly reverses the list iteratively and returns the new head?

hard

A. Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr != nullptr) { curr->next = prev; prev = curr; } return prev; }

B. Node* reverseList(Node* head) { Node* curr = head; Node* prev = nullptr; while (prev) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return curr; }

C. Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }

D. Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr != nullptr) { Node* next = curr->next; prev = curr; curr = next; } return prev; }

Solution

1. Step 1: Check pointer initialization and loop condition

   Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } initializes prev to nullptr, curr to head, and loops while curr is not null.

2. Step 2: Verify pointer updates inside loop

   Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } saves next, reverses curr->next, moves prev and curr forward correctly, then returns prev as new head.

3. Final Answer:

   Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } -> Option C

4. Quick Check:

   Correct pointer updates and return [OK]

Hint: Save next, reverse link, move prev and curr forward [OK]

Common Mistakes:

• Wrong loop condition
• Not saving next before changing links
• Returning wrong pointer