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

Concept Flow - Reverse a Singly Linked List Iterative

Start with head node

↓

Initialize prev = NULL, current = head

↓

While current != NULL

↓

Save next = current->next

↓

Reverse pointer: current->next = prev

↓

Move prev = current

↓

Move current = next

↓

Repeat loop

↓

Loop ends when current == NULL

↓

Return prev as new head

We start from the head and move through the list, reversing each node's pointer to point backward, until we reach the end. The prev pointer becomes the new head.

Execution Sample

DSA C

Node* reverseList(Node* head) {
  Node* prev = NULL;
  Node* current = head;
  while (current != NULL) {
    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
0	Initialize prev=NULL, current=head (1)	1 -> 2 -> 3 -> NULL	prev=NULL, current=1	1 -> 2 -> 3 -> NULL
1	Save next = current->next (2)	1 -> 2 -> 3 -> NULL	next=2	1 -> 2 -> 3 -> NULL
2	Reverse current->next to prev (NULL)	1 -> 2 -> 3 -> NULL	1->next=NULL	1 -> NULL 2 -> 3 -> NULL
3	Move prev = current (1)	1 -> 2 -> 3 -> NULL	prev=1	1 -> NULL 2 -> 3 -> NULL
4	Move current = next (2)	1 -> 2 -> 3 -> NULL	current=2	1 -> NULL 2 -> 3 -> NULL
5	Save next = current->next (3)	1 -> NULL 2 -> 3 -> NULL	next=3	1 -> NULL 2 -> 3 -> NULL
6	Reverse current->next to prev (1)	1 -> NULL 2 -> 3 -> NULL	2->next=1	2 -> 1 -> NULL 3 -> NULL
7	Move prev = current (2)	2 -> 1 -> NULL 3 -> NULL	prev=2	2 -> 1 -> NULL 3 -> NULL
8	Move current = next (3)	2 -> 1 -> NULL 3 -> NULL	current=3	2 -> 1 -> NULL 3 -> NULL
9	Save next = current->next (NULL)	2 -> 1 -> NULL 3 -> NULL	next=NULL	2 -> 1 -> NULL 3 -> NULL
10	Reverse current->next to prev (2)	2 -> 1 -> NULL 3 -> NULL	3->next=2	3 -> 2 -> 1 -> NULL
11	Move prev = current (3)	3 -> 2 -> 1 -> NULL	prev=3	3 -> 2 -> 1 -> NULL
12	Move current = next (NULL)	3 -> 2 -> 1 -> NULL	current=NULL	3 -> 2 -> 1 -> NULL
13	Loop ends, return prev as new head (3)	3 -> 2 -> 1 -> NULL	return prev	3 -> 2 -> 1 -> NULL

💡 current becomes NULL at step 12, loop ends, prev points to new head

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	Final
prev	NULL	1	2	3	3	3	3
current	1	2	3	NULL	NULL	NULL	NULL
next	undefined	2	3	NULL	NULL	NULL	NULL

Key Moments - 3 Insights

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

Because once we reverse current->next to prev, we lose the original next node. Saving 'next' first (see step 1 and 5) lets us continue traversing the list.

Why does the loop stop when current becomes NULL?

The loop condition is while(current != NULL). When current is NULL (step 12), it means we reached past the last node, so reversal is complete.

What does 'prev' point to at the end?

At the end (step 13), 'prev' points to the new head of the reversed list, which was the last node before reversal.

Visual Quiz - 3 Questions

Look at the execution table at step 6, what does node 2's next pointer point to?

A NULL

B Node 3

C Node 1

D Node 2 itself

💡 Hint

Check the 'Pointer Changes' column at step 6 where 2->next is set to 1.

At which step does the 'current' pointer become NULL?

A Step 12

B Step 10

C Step 13

D Step 9

💡 Hint

Look at the 'current' variable in variable_tracker and execution_table rows.

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

A List remains unchanged

B List is partially reversed or broken

C List becomes empty

D List is reversed correctly

💡 Hint

Refer to the importance of 'prev' updates in the execution_table steps 3, 7, and 11.

Concept Snapshot

Reverse a singly linked list iteratively:
- Use three pointers: prev (NULL), current (head), next (temp)
- Loop while current != NULL:
  * Save next = current->next
  * Reverse current->next = prev
  * Move prev = current
  * Move current = next
- Return prev as new head
This reverses links one by one, changing direction.

Full Transcript

This visualization shows how to reverse a singly linked list using an iterative method. We start with three pointers: prev set to NULL, current set to the head of the list, and next used to temporarily store the next node. In each step, we save the next node, reverse the current node's pointer to point to prev, then move prev and current forward. This continues until current becomes NULL, meaning we have processed all nodes. The prev pointer then points to the new head of the reversed list. The execution table tracks each step, showing how pointers change and how the list nodes rearrange visually. Key moments clarify why saving next is necessary before reversing, why the loop stops when current is NULL, and what prev points to at the end. The quiz tests understanding of pointer changes and loop termination. This method efficiently reverses the list in-place without extra memory.

Practice

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

easy

A. To delete all nodes from the linked list

B. To create a new linked list with reversed elements

C. To sort the linked list in ascending order

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

Solution

1. Step 1: Understand the linked list structure

   A singly linked list has nodes connected in one direction only, from head to tail.

2. Step 2: Purpose of iterative reversal

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

3. Final Answer:

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

4. Quick Check:

   Reversing means changing links direction [OK]

Hint: Reversing means flipping links, not creating new nodes [OK]

Common Mistakes:

• Thinking reversal creates a new list instead of changing links
• Confusing reversal with sorting
• Assuming nodes are deleted during reversal

2. Which of the following is the correct way to initialize pointers for iterative reversal of a singly linked list in C?

easy

A. struct Node *prev = NULL, *current = head, *next = NULL;

B. struct Node *prev = head, *current = NULL, *next = NULL;

C. struct Node *prev = NULL, *current = NULL, *next = head;

D. struct Node *prev = head, *current = head, *next = head;

Solution

1. Step 1: Identify starting pointers

   For reversal, prev starts as NULL because the new tail points to NULL, current starts at head to traverse.

2. Step 2: Correct initialization

   Next pointer is initialized as NULL and updated inside the loop; so initial next = NULL is correct.

3. Final Answer:

   struct Node *prev = NULL, *current = head, *next = NULL; -> Option A

4. Quick Check:

   Prev NULL, current head to start [OK]

Hint: Prev starts NULL, current starts at head [OK]

Common Mistakes:

• Setting prev to head initially
• Setting current to NULL at start
• Initializing next pointer incorrectly

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

medium

A. 2 -> 3 -> 1 -> NULL

B. 3 -> 2 -> 1 -> NULL

C. NULL -> 3 -> 2 -> 1

D. 1 -> 2 -> 3 -> NULL

Solution

1. Step 1: Trace reversal process

   Initially: 1->2->3->NULL. After reversal, links point backward: 3->2->1->NULL.

2. Step 2: Confirm final head

   The last node (3) becomes the new head, so output is 3->2->1->NULL.

3. Final Answer:

   3 -> 2 -> 1 -> NULL -> Option B

4. Quick Check:

   Reverse order of nodes [OK]

Hint: Reverse means last becomes first [OK]

Common Mistakes:

• Assuming list stays the same after reversal
• Confusing NULL placement
• Mixing node order incorrectly

4. Identify the error in this iterative reversal code snippet for a singly linked list in C:

struct Node* reverse(struct Node* head) {
  struct Node* prev = head;
  struct Node* current = head;
  struct Node* next = NULL;
  while (current != NULL) {
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

medium

A. prev should be initialized to NULL, not head

B. current should be initialized to NULL, not head

C. next pointer is not updated inside the loop

D. Function should return current, not prev

Solution

1. Step 1: Check pointer initialization

   Prev must start as NULL because the new tail node points to NULL, not head.

2. Step 2: Analyze loop pointer updates

   Current and next are correctly updated; only prev initialization is wrong.

3. Final Answer:

   prev should be initialized to NULL, not head -> Option A

4. Quick Check:

   Prev NULL to mark new tail [OK]

Hint: Prev must start NULL to avoid cycle [OK]

Common Mistakes:

• Starting prev at head causing cycle
• Not updating next inside loop
• Returning wrong pointer at end

5. Given a singly linked list with nodes containing values 10 -> 20 -> 30 -> 40 -> NULL, write the final linked list after applying iterative reversal twice in a row.

hard

A. NULL

B. 40 -> 30 -> 20 -> 10 -> NULL

C. 10 -> 20 -> 30 -> 40 -> NULL

D. 20 -> 10 -> 40 -> 30 -> NULL

Solution

1. Step 1: Reverse the list once

   Original: 10->20->30->40->NULL. After first reversal: 40->30->20->10->NULL.

2. Step 2: Reverse the reversed list again

   Reversing 40->30->20->10->NULL returns it to original: 10->20->30->40->NULL.

3. Final Answer:

   10 -> 20 -> 30 -> 40 -> NULL -> Option C

4. Quick Check:

   Double reversal restores original list [OK]

Hint: Reversing twice returns original list [OK]

Common Mistakes:

• Assuming double reversal changes list order
• Confusing node values after reversal
• Forgetting NULL at list end