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

Concept Flow - Reverse a Singly Linked List Iterative

Start with head node

↓

Initialize prev = nil, current = head

↓

While current != nil

↓

Save next = current.next

↓

Reverse current.next to prev

↓

Move prev to current

↓

Move current to next

Back to While↓

End: prev is new head

↩Back to While

Start from the head, reverse each node's pointer to previous, move forward until all nodes are reversed.

Execution Sample

DSA Go

func reverseList(head *Node) *Node {
  var prev *Node = nil
  current := head
  for current != nil {
    next := current.Next
    current.Next = prev
    prev = current
    current = next
  }
  return prev
}

This code reverses a singly linked list by changing each node's next pointer to the previous node iteratively.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
0	Start	1 -> 2 -> 3 -> nil	prev = nil, current = 1	1 -> 2 -> 3 -> nil
1	Save next	1 -> 2 -> 3 -> nil	next = 2	1 -> 2 -> 3 -> nil
2	Reverse pointer	1 -> 2 -> 3 -> nil	1.Next = prev(nil)	1 -> nil, 2 -> 3 -> nil
3	Move prev	1 -> nil, 2 -> 3 -> nil	prev = 1	1 -> nil, 2 -> 3 -> nil
4	Move current	1 -> nil, 2 -> 3 -> nil	current = 2	1 -> nil, 2 -> 3 -> nil
5	Save next	1 -> nil, 2 -> 3 -> nil	next = 3	1 -> nil, 2 -> 3 -> nil
6	Reverse pointer	1 -> nil, 2 -> 3 -> nil	2.Next = prev(1)	2 -> 1 -> nil, 3 -> nil
7	Move prev	2 -> 1 -> nil, 3 -> nil	prev = 2	2 -> 1 -> nil, 3 -> nil
8	Move current	2 -> 1 -> nil, 3 -> nil	current = 3	2 -> 1 -> nil, 3 -> nil
9	Save next	2 -> 1 -> nil, 3 -> nil	next = nil	2 -> 1 -> nil, 3 -> nil
10	Reverse pointer	2 -> 1 -> nil, 3 -> nil	3.Next = prev(2)	3 -> 2 -> 1 -> nil
11	Move prev	3 -> 2 -> 1 -> nil	prev = 3	3 -> 2 -> 1 -> nil
12	Move current	3 -> 2 -> 1 -> nil	current = nil	3 -> 2 -> 1 -> nil
13	End	3 -> 2 -> 1 -> nil	Return prev (3)	3 -> 2 -> 1 -> nil

💡 current becomes nil at step 12, loop ends, prev is new head

Variable Tracker

Variable	Start	After 1	After 2	After 3	Final
prev	nil	1	2	3	3
current	1	2	3	nil	nil
next	undefined	2	3	nil	nil

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, 5, 9) keeps track of the next node to process.

Why does the loop stop when current is nil, not when prev is nil?

The loop moves current forward each time. When current is nil (step 12), it means we have processed all nodes. Prev holds the new head after reversal.

What does the visual state show after reversing a pointer?

It shows the partial reversed list starting from prev, and the remaining unreversed nodes starting from current (see steps 2, 6, 10).

Visual Quiz - 3 Questions

Look at the execution table at step 6, what is the visual state of the list?

A 2 -> 1 -> nil, 3 -> nil

B 3 -> 2 -> 1 -> nil

C 1 -> nil, 2 -> 3 -> nil

D 1 -> 2 -> 3 -> nil

💡 Hint

Check the 'Visual State' column at step 6 in the execution_table.

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

A Step 10

B Step 11

C Step 12

D Step 13

💡 Hint

Look at the 'Pointer Changes' column for 'current' in the execution_table.

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

A The list remains unchanged

B The reversed list will be empty

C The list is reversed correctly

D The reversed list will only contain the last node

💡 Hint

Refer to variable_tracker for 'prev' updates and execution_table steps where 'prev' moves.

Concept Snapshot

Reverse a singly linked list iteratively:
- Use three pointers: prev (nil), current (head), next
- Loop while current != nil:
  * Save next = current.Next
  * Reverse current.Next to prev
  * Move prev to current
  * Move current to next
- Return prev as new head
- Time: O(n), Space: O(1)

Full Transcript

To reverse a singly linked list iteratively, we start with three pointers: prev set to nil, current set to the head of the list, and next to temporarily hold the next node. We loop while current is not nil. In each iteration, we save current.Next in next, then reverse current.Next to point to prev. We then move prev to current and current to next. This process continues until current becomes nil, meaning all nodes have been reversed. Finally, prev points to the new head of the reversed list. This method reverses the list in place with O(n) time and O(1) space complexity.

Practice

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

easy

A. To sort the linked list in ascending order

B. To create a new linked list with reversed elements

C. To delete all nodes and recreate them in reverse 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 pointing to the next node only, so reversing means changing these pointers.

2. Step 2: Purpose of iterative reversal

   The iterative method changes the next pointer of each node to point to the previous node, reversing the list in place.

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 it creates a new list instead of reversing in place
• Confusing reversal with sorting
• Assuming nodes are deleted and recreated

2. Which of the following Go code snippets correctly initializes pointers for iterative reversal of a singly linked list?

easy

A. var prev = head; current := nil

B. var prev *Node = nil; current := head

C. prev := head; current := head.next

D. var prev *Node = head; current := head

Solution

1. Step 1: Initialization for reversal

   We start with prev as nil because the new tail will point to nil, and current at head to traverse the list.

2. Step 2: Check each option

   var prev *Node = nil; current := head correctly sets prev to nil and current to head. Others incorrectly assign prev or current.

3. Final Answer:

   var prev *Node = nil; current := head -> Option B

4. Quick Check:

   Prev starts nil, current at head [OK]

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

Common Mistakes:

• Setting prev to head initially
• Setting current to nil at start
• Mixing pointer assignments

3. What will be the output linked list after running this Go code to reverse a singly linked list?

type Node struct {
    Val  int
    Next *Node
}

func reverseList(head *Node) *Node {
    var prev *Node = nil
    current := head
    for current != nil {
        nextTemp := current.Next
        current.Next = prev
        prev = current
        current = nextTemp
    }
    return prev
}

// Input list: 1 -> 2 -> 3 -> nil
// Call: reverseList(head)

medium

A. 3 -> 2 -> 1 -> nil

B. 1 -> 2 -> 3 -> nil

C. nil -> 3 -> 2 -> 1

D. 3 -> 1 -> 2 -> nil

Solution

1. Step 1: Trace the reversal loop

   Initially prev=nil, current=1. Each iteration reverses current.Next to prev and moves pointers forward.

2. Step 2: Final reversed list

   After loop, prev points to node with Val=3, linked as 3->2->1->nil.

3. Final Answer:

   3 -> 2 -> 1 -> nil -> Option A

4. Quick Check:

   Reversed list order is 3,2,1 [OK]

Hint: Follow pointer changes step-by-step [OK]

Common Mistakes:

• Confusing original and reversed order
• Misunderstanding pointer updates
• Assuming list remains unchanged

4. Identify the error in this Go code snippet for reversing a singly linked list iteratively:

func reverseList(head *Node) *Node {
    var prev *Node = head
    current := head
    for current != nil {
        nextTemp := current.Next
        current.Next = prev
        prev = current
        current = nextTemp
    }
    return prev
}

medium

A. prev should be initialized to nil, not head

B. current should be initialized to nil

C. nextTemp should be initialized outside the loop

D. The function should return current, not prev

Solution

1. Step 1: Check initialization of prev

   Prev must start as nil because the new tail's next is nil. Setting prev=head causes a cycle.

2. Step 2: Effect of wrong prev initialization

   Setting prev=head makes current.Next point to itself on first iteration, causing infinite loop or wrong reversal.

3. Final Answer:

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

4. Quick Check:

   Prev starts nil to avoid cycles [OK]

Hint: Prev must start nil to break old links [OK]

Common Mistakes:

• Initializing prev to head causing cycles
• Returning current instead of prev
• Misplacing nextTemp initialization

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

hard

A. 40 -> 30 -> 20 -> 10 -> nil

B. nil

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

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

Solution

1. Step 1: First reversal

   Reversing 10->20->30->40->nil gives 40->30->20->10->nil.

2. Step 2: Second reversal

   Reversing again restores original order: 10->20->30->40->nil.

3. Final Answer:

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

4. Quick Check:

   Double reversal returns original list [OK]

Hint: Reversing twice returns original list [OK]

Common Mistakes:

• Assuming second reversal changes order differently
• Confusing node values after reversal
• Thinking list becomes empty