Reverse a Singly Linked List Iterative in DSA Java - 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 link: current.next = prev

↓

Move prev = current

↓

Move current = next

↓

Repeat loop

↓

Loop ends when current == null

↓

Return prev as new head

Start from the head, reverse each node's pointer one by one until the end, then return the new head.

Execution Sample

DSA Java

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 iteratively.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
0	Start with list head	1 -> 2 -> 3 -> null	prev = null, current = 1	1 -> 2 -> 3 -> null
1	Save next = current.next	1 -> 2 -> 3 -> null	next = 2	1 -> 2 -> 3 -> null
2	Reverse current.next to prev	1 -> 2 -> 3 -> null	1.next = null	1 -> null 2 -> 3 -> null
3	Move prev and current forward	1 -> null 2 -> 3 -> null	prev = 1, current = 2	1 -> null 2 -> 3 -> null
4	Save next = current.next	1 -> null 2 -> 3 -> null	next = 3	1 -> null 2 -> 3 -> null
5	Reverse current.next to prev	1 -> null 2 -> 3 -> null	2.next = 1	2 -> 1 -> null 3 -> null
6	Move prev and current forward	2 -> 1 -> null 3 -> null	prev = 2, current = 3	2 -> 1 -> null 3 -> null
7	Save next = current.next	2 -> 1 -> null 3 -> null	next = null	2 -> 1 -> null 3 -> null
8	Reverse current.next to prev	2 -> 1 -> null 3 -> null	3.next = 2	3 -> 2 -> 1 -> null
9	Move prev and current forward	3 -> 2 -> 1 -> null	prev = 3, current = null	3 -> 2 -> 1 -> null
10	Loop ends, return prev as new head	3 -> 2 -> 1 -> null	Return 3	3 -> 2 -> 1 -> null

💡 current becomes null at step 9, loop ends and prev is new head

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	Final
prev	null	1	2	3	3
current	1	2	3	null	null
next	undefined	2	3	null	null

Key Moments - 3 Insights

Why do we set current.next = prev instead of prev.next = current?

Because we want to reverse the link direction. Setting current.next = prev changes the pointer of the current node to point backward. prev.next = current would create a cycle and not reverse the list. See execution_table rows 2, 5, and 8.

Why do we need to save next = current.next before reversing the link?

Because once we reverse current.next to prev, we lose the original next node. Saving next before reversing lets us continue traversing the list. See execution_table rows 1, 4, and 7.

Why does the loop stop when current becomes null?

Because current null means we have processed all nodes. At this point, prev points to the new head of the reversed list. See execution_table row 9 and exit_note.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the visual state of the list?

A 3 -> 2 -> 1 -> null

B 1 -> 2 -> 3 -> null

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

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

💡 Hint

Check the Visual State column at step 5 in execution_table.

At which step does current become null, ending the loop?

A Step 6

B Step 9

C Step 3

D Step 10

💡 Hint

Look at the Pointer Changes and Operation columns to find when current is set to null.

If we forget to save next before reversing, what happens in the execution?

A We lose access to the rest of the list and cannot continue traversal.

B The list reverses correctly anyway.

C The prev pointer becomes null.

D The loop never ends.

💡 Hint

Refer to key_moments question 2 about saving next before reversing.

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 to prev
  - Move prev = current, current = next
- Return prev as new head
This reverses links one by one without extra space.

Full Transcript

To reverse a singly linked list iteratively, we start with three pointers: prev set to null, current set to the head of the list, and next as a temporary pointer. We loop while current is not null. In each iteration, we save the next node, reverse the current node's next pointer to point to prev, then move prev and current forward by one node. When current becomes null, prev points to the new head of the reversed list. This method changes the direction of the links step-by-step without using extra memory. Key points include saving the next node before reversing to avoid losing access, and understanding that reversing means changing current.next to prev, not the other way around.

Practice

1. What is the main purpose of reversing a singly linked list iteratively?

easy

A. To sort the list in ascending order

B. To delete all nodes from the list

C. To change the direction of all links so the last node becomes the first

D. To add a new node at the end of the list

Solution

1. Step 1: Understand the linked list structure

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

2. Step 2: Purpose of reversing

   Reversing changes the links so the last node points to the previous one, making it the new head.

3. Final Answer:

   To change the direction of all links so the last node becomes the first -> Option C

4. Quick Check:

   Reversing = changing link directions [OK]

Hint: Reversing flips the list direction, last becomes first [OK]

Common Mistakes:

• Confusing reversing with sorting
• Thinking reversing deletes nodes
• Assuming reversing adds nodes

2. Which of the following is the correct way to initialize the previous pointer before starting the iterative reversal?

easy

A. Node prev = head;

B. Node prev = head.next;

C. Node prev = new Node();

D. Node prev = null;

Solution

1. Step 1: Understand the role of previous pointer

   Previous pointer starts as null because the new tail's next should be null after reversal.

2. Step 2: Initialization

   Setting prev to null ensures the first node processed points to null, ending the reversed list properly.

3. Final Answer:

   Node prev = null; -> Option D

4. Quick Check:

   Prev starts null to mark new tail [OK]

Hint: Prev pointer starts null to mark list end [OK]

Common Mistakes:

• Initializing prev to head causes cycle
• Creating new node wastes memory
• Starting prev at head.next skips first node

3. What will be the output linked list after reversing the list 1 -> 2 -> 3 -> null iteratively?

medium

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

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

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

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

Solution

1. Step 1: Trace the reversal process

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

2. Step 2: Confirm final head and tail

   Node 3 becomes new head, node 1 becomes tail pointing to null.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option B

4. Quick Check:

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

Hint: Last node becomes first after reversal [OK]

Common Mistakes:

• Assuming list stays same after reversal
• Confusing null placement
• Mixing node order

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

Node prev = head;
Node current = head.next;
while (current != null) {
  Node nextNode = current.next;
  current.next = prev;
  prev = current;
  current = nextNode;
}
head.next = null;
head = prev;

medium

A. prev should be initialized to null, not head

B. current should start at head, not head.next

C. head.next should not be set to null

D. Loop condition should be current.next != null

Solution

1. Step 1: Check initialization of prev pointer

   Prev must start as null to mark new tail's next as null after reversal.

2. Step 2: Effect of wrong initialization

   Starting prev at head causes a cycle, breaking reversal logic.

3. Final Answer:

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

4. Quick Check:

   Prev = null to avoid cycles [OK]

Hint: Prev must start null to avoid cycles [OK]

Common Mistakes:

• Starting prev at head causes infinite loop
• Wrong loop condition misses last node
• Forgetting to set old head next to null

5. Given a singly linked list with nodes containing values 10 -> 20 -> 30 -> 40 -> null, which iterative code snippet correctly reverses it and prints the reversed list?

hard

A. Node prev = null;
Node current = head;
while (current != null) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
// Print list starting from head

B. Node prev = head;
Node current = head.next;
while (current != null) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
// Print list starting from head

C. Node current = head;
while (current != null) {
Node next = current.next;
current.next = null;
current = next;
}
// Print list starting from head

D. Node prev = null;
Node current = head;
while (current.next != null) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
// Print list starting from head

Solution

1. Step 1: Verify initialization of pointers

   Prev must start as null, current at head to reverse all nodes correctly.

2. Step 2: Check loop condition and pointer updates

   Loop runs while current != null to process all nodes; inside loop, links reversed properly.

3. Step 3: Confirm final head assignment and printing

   After loop, head is set to prev (new head). Printing from head shows reversed list.

4. Final Answer:

   Option A code correctly reverses and prints the list -> Option A

5. Quick Check:

   Prev=null, loop full list, head=prev [OK]

Hint: Prev null, loop full list, head = prev after reversal [OK]

Common Mistakes:

• Starting prev at head causes cycle
• Loop condition misses last node
• Setting current.next = null inside loop breaks links