Reverse a Singly Linked List Iterative in DSA Go - Deep Dive

Overview - Reverse a Singly Linked List Iterative

What is it?

Reversing a singly linked list iteratively means changing the direction of the links between nodes so that the last node becomes the first, and the first becomes the last. Instead of using extra memory or recursion, this method uses a simple loop to rearrange the pointers step-by-step. It transforms the list in place, without creating new nodes. This is a common operation to understand how linked lists work and to manipulate their order.

Why it matters

Without the ability to reverse a linked list, many algorithms and applications that rely on changing data order would be inefficient or impossible. For example, undo features, reversing sequences, or preparing data for certain algorithms depend on this operation. If we couldn't reverse lists efficiently, programs would use more memory or run slower, making software less responsive and more resource-heavy.

Where it fits

Before learning this, you should understand what a singly linked list is and how nodes connect with pointers. After mastering iterative reversal, you can explore recursive reversal methods, doubly linked lists, and more complex list manipulations like sorting or merging.

Mental Model

Core Idea

Reversing a singly linked list iteratively means walking through the list once and flipping each node's pointer to point backward instead of forward.

Think of it like...

Imagine walking down a line of dominoes and turning each one around so it faces the opposite direction, one by one, until the whole line faces backward.

Original list:
head -> [1] -> [2] -> [3] -> [4] -> null

Step-by-step reversal:
prev = null
curr = head

Iteration 1:
curr = [1], next = [2]
[1].next = prev (null)
prev = [1]
curr = [2]

Iteration 2:
curr = [2], next = [3]
[2].next = prev ([1])
prev = [2]
curr = [3]

Iteration 3:
curr = [3], next = [4]
[3].next = prev ([2])
prev = [3]
curr = [4]

Iteration 4:
curr = [4], next = null
[4].next = prev ([3])
prev = [4]
curr = null

Result:
head -> [4] -> [3] -> [2] -> [1] -> null

Build-Up - 7 Steps

1

Foundation

Understanding Singly Linked Lists

Concept: Learn what a singly linked list is and how nodes connect using pointers.

A singly linked list is a chain of nodes where each node holds data and a pointer to the next node. The last node points to null, marking the end. You can only move forward from one node to the next. For example, a list with nodes 1 -> 2 -> 3 means node 1 points to node 2, which points to node 3, which points to null.

Result

You can visualize and traverse a singly linked list from the head node to the end by following next pointers.

Understanding the basic structure of singly linked lists is essential because reversing them means changing these next pointers carefully.

2

Foundation

Pointers and Node References

Concept: Learn how to use pointers to access and change node connections.

Each node has a pointer called 'next' that tells where the next node is. By changing this pointer, you can change the order of nodes. For example, if node A points to node B, changing A.next to point to node C instead will skip B. This is how we can rearrange nodes without moving data.

Result

You can manipulate the list structure by changing node pointers, which is the key to reversing the list.

Knowing how to safely change pointers without losing access to nodes prevents breaking the list during reversal.

3

Intermediate

Iterative Reversal Algorithm Steps

🤔Before reading on: do you think reversing requires creating new nodes or can it be done by changing pointers only? Commit to your answer.

Concept: Introduce the step-by-step process to reverse the list by changing pointers iteratively.

Start with three pointers: prev (initially null), curr (starting at head), and next (to store curr.next). In each step, save curr.next in next, then point curr.next to prev, move prev to curr, and curr to next. Repeat until curr is null. Finally, prev points to the new head of the reversed list.

Result

The list is reversed in place with a single pass and no extra memory for new nodes.

Understanding this pointer juggling is crucial because it shows how to reverse the list efficiently without extra space.

4

Intermediate

Go Code Implementation

🤔Before reading on: do you think the code needs recursion or can a simple loop handle reversal? Commit to your answer.

Concept: Translate the iterative reversal logic into Go code with clear comments.

type ListNode struct { Val int Next *ListNode } func reverseList(head *ListNode) *ListNode { var prev *ListNode = nil curr := head for curr != nil { next := curr.Next // Save next node curr.Next = prev // Reverse pointer prev = curr // Move prev forward curr = next // Move curr forward } return prev // New head }

Result

The function returns the head of the reversed list, which points to nodes in reverse order.

Seeing the code helps connect the mental model to actual implementation, reinforcing how pointer changes work in practice.

5

Intermediate

Dry Run with Example List

🤔Before reading on: predict the output list after reversing 1->2->3->null. Commit to your answer.

Concept: Walk through the code step-by-step with a simple list to see how pointers change.

Given list: 1 -> 2 -> 3 -> null Initial: prev = null, curr = 1 Iteration 1: next = 2 1.next = null prev = 1 curr = 2 Iteration 2: next = 3 2.next = 1 prev = 2 curr = 3 Iteration 3: next = null 3.next = 2 prev = 3 curr = null Return prev (3) Final list: 3 -> 2 -> 1 -> null

Result

The reversed list is 3 -> 2 -> 1 -> null.

Dry running confirms the algorithm's correctness and builds confidence in pointer manipulation.

6

Advanced

Handling Edge Cases Safely

🤔Before reading on: do you think reversing an empty or single-node list needs special code? Commit to your answer.

Concept: Learn how the algorithm naturally handles empty and single-node lists without extra checks.

If the list is empty (head is nil), the loop never runs and returns nil, which is correct. If the list has one node, the loop runs once, sets its next to nil (which it already is), and returns the same node. No special code is needed to handle these cases.

Result

The reversal function works correctly for empty and single-node lists without modification.

Knowing that the algorithm gracefully handles edge cases prevents unnecessary code and bugs.

7

Expert

Performance and Memory Considerations

🤔Before reading on: do you think iterative reversal uses extra memory proportional to list size? Commit to your answer.

Concept: Understand the time and space complexity and why iterative reversal is efficient in practice.

The iterative reversal runs in O(n) time because it visits each node once. It uses O(1) extra space since it only stores a few pointers regardless of list size. This makes it very efficient compared to recursive reversal, which uses O(n) stack space. This efficiency is critical in systems with limited memory or large lists.

Result

Iterative reversal is fast and memory-friendly, suitable for production use.

Recognizing the efficiency advantages guides choosing iterative reversal in real-world applications.

Under the Hood

Internally, the reversal works by changing the 'next' pointer of each node to point to its previous node instead of the next. The algorithm keeps track of three pointers: prev, curr, and next. At each step, it saves the next node, reverses the current node's pointer, then moves forward. This pointer manipulation changes the linked list's direction without creating or deleting nodes.

Why designed this way?

This method was designed to reverse lists in place with minimal memory use and linear time. Alternatives like recursion use extra stack space and can cause stack overflow on large lists. Creating new lists wastes memory and time. The iterative approach balances simplicity, efficiency, and safety, making it the standard solution.

┌─────────┐     ┌─────────┐     ┌─────────┐     ┌─────────┐
│  Node1  │ --> │  Node2  │ --> │  Node3  │ --> │  null   │
└─────────┘     └─────────┘     └─────────┘     └─────────┘

Pointers:
prev = null
curr = Node1
next = curr.Next (Node2)

After first iteration:
Node1.next = prev (null)
prev = Node1
curr = Node2

Repeat until curr is null.

Result:
prev points to Node3, which points to Node2, which points to Node1, which points to null.

Myth Busters - 3 Common Misconceptions

Quick: Does reversing a singly linked list require creating new nodes? Commit to yes or no.

Common Belief: Reversing a singly linked list means creating a new list with nodes in reverse order.

Reality: Reversal changes the existing nodes' pointers in place without creating new nodes.

Why it matters: Creating new nodes wastes memory and time, making reversal inefficient and unnecessary.

Quick: Can you reverse a singly linked list by just swapping node values? Commit to yes or no.

Common Belief: Swapping the values inside nodes is enough to reverse the list.

Reality: Swapping values changes data but does not reverse the list structure; the pointers remain the same.

Why it matters: This misconception leads to incorrect reversal that doesn't change node order, breaking algorithms relying on pointer structure.

Quick: Does iterative reversal use extra memory proportional to list size? Commit to yes or no.

Common Belief: Iterative reversal requires extra memory for each node to store reversed pointers.

Reality: Iterative reversal uses only a few pointer variables, constant extra memory regardless of list size.

Why it matters: Believing extra memory is needed may discourage using the efficient iterative method.

Expert Zone

1

The order of pointer updates is critical; changing curr.Next before saving next causes loss of access to the rest of the list.

2

Reversal can be combined with other list operations in a single pass for optimization, such as detecting cycles or splitting lists.

3

In concurrent environments, reversing a list requires careful synchronization to avoid race conditions on pointers.

When NOT to use

Avoid iterative reversal if the list is immutable or shared concurrently without locks. In such cases, create a new reversed list or use functional data structures. Also, recursive reversal may be preferred for educational clarity despite its memory cost.

Production Patterns

Iterative reversal is used in undo stacks, reversing playback queues, and preparing data for algorithms like palindrome checks or list-based sorting. It is often combined with other pointer manipulations in linked list libraries and system-level code.

Connections

Stack Data Structure

Reversing a linked list is conceptually similar to pushing nodes onto a stack and then popping them to get reversed order.

Understanding stacks helps grasp how reversal changes order by last-in-first-out logic, which is the essence of pointer reversal.

Pointer Manipulation in C Programming

Both involve careful handling of memory addresses to change data structure layouts safely.

Mastering pointer manipulation in linked list reversal builds foundational skills for low-level programming and memory management.

Undo Mechanism in Text Editors

Reversing linked lists underlies how undo stacks reverse user actions in order.

Knowing list reversal clarifies how software tracks and reverses changes efficiently.

Common Pitfalls

#1 Losing access to the rest of the list by changing pointers in the wrong order.

Wrong approach:

for curr != nil {
curr.Next = prev
prev = curr
curr = curr.Next // WRONG: curr.Next was changed above
}

Correct approach:

for curr != nil {
next := curr.Next
curr.Next = prev
prev = curr
curr = next
}

Root cause:

Not saving the next node before changing curr.Next causes loss of the remaining list.

#2 Trying to reverse by swapping node values instead of pointers.

Wrong approach:

func reverseList(head *ListNode) *ListNode {
// Swap values only
// This does not reverse pointers
return head
}

Correct approach:

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

Root cause:

Confusing data reversal with pointer reversal leads to incorrect list order.

#3 Not handling empty list input, causing nil pointer errors.

Wrong approach:

func reverseList(head *ListNode) *ListNode {
curr := head
curr.Next = nil // panic if head is nil
return curr
}

Correct approach:

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

Root cause:

Not checking for nil head causes runtime errors.

Key Takeaways

Reversing a singly linked list iteratively changes the direction of node pointers in a single pass without extra memory.

The algorithm uses three pointers--prev, curr, and next--to safely reverse links without losing access to nodes.

It naturally handles edge cases like empty or single-node lists without special code.

Understanding pointer manipulation is essential to avoid common mistakes like losing the rest of the list.

Iterative reversal is efficient and widely used in real-world applications requiring data order changes.

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