Reverse a Singly Linked List Iterative in DSA C++ - Execution Trace

Concept Flow - Reverse a Singly Linked List Iterative

Start: head points to first node

↓

Initialize prev = nullptr, current = head

↓

Loop while current != nullptr

↓

Save next = current->next

↓

Reverse link: current->next = prev

↓

Move prev = current

↓

Move current = next

↓

Repeat loop

↓

Loop ends when current == nullptr

↓

Set head = prev (new head)

↓

Done: list reversed

We start with pointers prev and current. We reverse each node's next pointer to point backward, moving forward until all nodes are reversed.

Execution Sample

DSA C++

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

This code reverses a singly linked list by changing the next pointers of each node iteratively.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize prev=nullptr, current=head (1)	1 -> 2 -> 3 -> null	prev=nullptr, current=1	1 -> 2 -> 3 -> null
2	Save next = current->next (2)	1 -> 2 -> 3 -> null	next=2	1 -> 2 -> 3 -> null
3	Reverse current->next = prev	1 -> 2 -> 3 -> null	1->next=nullptr	1 -> null 2 -> 3 -> null
4	Move prev = current	1 -> null 2 -> 3 -> null	prev=1	1 -> null 2 -> 3 -> null
5	Move current = next	1 -> null 2 -> 3 -> null	current=2	1 -> null 2 -> 3 -> null
6	Save next = current->next (3)	1 -> null 2 -> 3 -> null	next=3	1 -> null 2 -> 3 -> null
7	Reverse current->next = prev	1 -> null 2 -> 3 -> null	2->next=1	2 -> 1 -> null 3 -> null
8	Move prev = current	2 -> 1 -> null 3 -> null	prev=2	2 -> 1 -> null 3 -> null
9	Move current = next	2 -> 1 -> null 3 -> null	current=3	2 -> 1 -> null 3 -> null
10	Save next = current->next (null)	2 -> 1 -> null 3 -> null	next=nullptr	2 -> 1 -> null 3 -> null
11	Reverse current->next = prev	2 -> 1 -> null 3 -> null	3->next=2	3 -> 2 -> 1 -> null
12	Move prev = current	3 -> 2 -> 1 -> null	prev=3	3 -> 2 -> 1 -> null
13	Move current = next	3 -> 2 -> 1 -> null	current=nullptr	3 -> 2 -> 1 -> null
14	Loop ends, set head = prev	3 -> 2 -> 1 -> null	head=3	3 -> 2 -> 1 -> null

💡 current becomes nullptr, loop ends, head updated to prev which is new head

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 13	Final
prev	nullptr	nullptr	1	2	3	3
current	1	1	2	3	nullptr	nullptr
next	undefined	2	2	3	nullptr	nullptr
head	1	1	1	1	1	3

Key Moments - 3 Insights

Why do we need to save 'next' before reversing the link?

Because after reversing current->next to prev, we lose the original next node. Saving 'next' first lets us continue traversal. See execution_table steps 2 and 3.

Why does the loop stop when current is nullptr, not when current->next is nullptr?

We must process the last node too. If we stop at current->next == nullptr, the last node won't be reversed. The loop ends only when current is nullptr (step 13).

How does the head pointer change after reversal?

Initially head points to first node. After reversal, head is updated to prev, which points to the last processed node (new head). See step 14.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what does current->next point to?

A node 1

B node 3

C nullptr

D node 2

💡 Hint

Check 'Pointer Changes' column at step 7 where 2->next=1

At which step does current become nullptr?

A Step 11

B Step 13

C Step 12

D Step 14

💡 Hint

Look at 'current' variable in variable_tracker after step 13

If we forget to update prev = current inside the loop, what happens to the list?

A List fully reversed

B List partially reversed

C List remains unchanged

D List becomes empty

💡 Hint

Without updating prev, current->next always points to old prev=nullptr, so no reversal happens

Concept Snapshot

Reverse a singly linked list iteratively:
- Use three pointers: prev (nullptr), current (head), next
- Loop while current != nullptr:
  * Save next = current->next
  * Reverse link: current->next = prev
  * Move prev = current, current = next
- After loop, head = prev (new head)
- Result: list reversed in-place without extra memory

Full Transcript

This concept shows how to reverse a singly linked list using an iterative method. We start with two pointers: prev set to nullptr and current set to the head of the list. In each step, we save the next node to continue traversal after reversing the current node's next pointer to point backward to prev. Then we move prev and current forward. This continues until current becomes nullptr, meaning we have processed all nodes. Finally, we update the head pointer to prev, which is the new head of the reversed list. The execution table tracks each step, showing how nodes and pointers change. Key moments clarify why saving next is necessary before reversing links, why the loop stops when current is nullptr, and how the head pointer updates. The visual quiz tests understanding of pointer changes and loop termination. This method reverses the list in-place efficiently.

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