Reverse a Singly Linked List Iterative in DSA Typescript - 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. A singly linked list is a chain of nodes where each node points to the next one. This operation is done step-by-step using a loop without recursion. It helps us understand how to manipulate pointers and change the order of elements in a list.

Why it matters

Without the ability to reverse a linked list, many algorithms and data manipulations would be inefficient or impossible. For example, reversing helps in undo operations, palindrome checks, and reordering data. If we couldn't reverse lists, we would have to create new lists or use extra memory, making programs slower and more complex.

Where it fits

Before learning this, you should understand what a singly linked list is and how to traverse it. After mastering iterative reversal, you can learn recursive reversal, doubly linked lists, and advanced linked list problems like cycle detection or merging sorted lists.

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 a line of people holding hands forward. Reversing the list is like asking each person to let go of the hand in front and hold the hand behind instead, so the line flips direction.

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

Step-by-step reversal:
prev = null, current = head

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

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

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

Iteration 4:
current = [4], next = null
[4].next = prev ([3])
prev = [4]
current = 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.

A singly linked list is a chain of nodes. Each node has two parts: a value and a pointer to the next node. The last node points to null, meaning the end of the list. You can move through the list by following these pointers from the head node.

Result

You can visualize a list like: head -> [value|next] -> [value|next] -> ... -> null

Understanding the structure of singly linked lists is essential because reversing changes how these pointers connect nodes.

2

Foundation

Traversing a Linked List Iteratively

Concept: Learn how to move through a linked list using a loop.

Start at the head node. While the current node is not null, process the node (e.g., print its value), then move to the next node by following the current node's next pointer. Repeat until you reach null.

Result

You can visit all nodes in order: 1 -> 2 -> 3 -> 4 -> null

Knowing how to traverse a list iteratively is the base skill needed to manipulate pointers during reversal.

3

Intermediate

Reversing Pointers Step-by-Step

🤔Before reading on: Do you think you can reverse the list by changing each node's next pointer to the previous node in one pass? Commit to yes or no.

Concept: Change each node's next pointer to point to the previous node instead of the next one.

Use three variables: prev (starts as null), current (starts at head), and next (to store current.next). For each node, save current.next in next, then set current.next to prev. Move prev to current, and current to next. Repeat until current is null.

Result

The list pointers are reversed, so the last node becomes the new head.

Understanding pointer reassignment in one pass avoids extra memory and makes reversal efficient.

4

Intermediate

Implementing Iterative Reversal in TypeScript

🤔Before reading on: Do you think the head pointer should be updated inside or after the loop? Commit to your answer.

Concept: Write code that uses a loop to reverse the list and returns the new head.

class ListNode { value: number; next: ListNode | null; constructor(value: number, next: ListNode | null = null) { this.value = value; this.next = next; } } function reverseList(head: ListNode | null): ListNode | null { let prev: ListNode | null = null; let current = head; while (current !== null) { const next = current.next; current.next = prev; prev = current; current = next; } return prev; }

Result

Calling reverseList on head of 1->2->3->null returns new head 3->2->1->null

Knowing when and how to update the head pointer is key to returning the reversed list correctly.

5

Intermediate

Dry Run with Example List

🤔Before reading on: After reversing 1->2->3->null, what is the new head value? Commit to your answer.

Concept: Walk through the code with a small list to see pointer changes at each step.

Start: prev = null, current = [1] Iteration 1: next = [2], [1].next = null, prev = [1], current = [2] Iteration 2: next = [3], [2].next = [1], prev = [2], current = [3] Iteration 3: next = null, [3].next = [2], prev = [3], current = null Return prev as new head.

Result

New list: 3 -> 2 -> 1 -> null

Dry running helps visualize pointer changes and confirms the algorithm works as intended.

6

Advanced

Handling Edge Cases and Empty Lists

🤔Before reading on: What happens if the input list is empty or has one node? Commit to your answer.

Concept: Ensure the reversal code works correctly when the list is empty or has only one node.

If head is null, the loop never runs and null is returned. If the list has one node, the loop runs once, sets next to null, current.next to null (prev), and returns the single node as new head.

Result

Empty list returns null; single-node list returns the same node unchanged.

Knowing how edge cases behave prevents bugs and crashes in real programs.

7

Expert

Performance and Memory Considerations

🤔Before reading on: Does iterative reversal use extra memory proportional to list size? Commit to your answer.

Concept: Analyze time and space complexity and why iterative reversal is efficient.

The algorithm runs in O(n) time because it visits each node once. It uses O(1) extra space since it only stores a few pointers, not new nodes or arrays. This makes it memory efficient compared to recursive reversal, which uses call stack space.

Result

Iterative reversal is fast and uses minimal memory, suitable for large lists.

Understanding complexity helps choose the best reversal method for performance-critical applications.

Under the Hood

Internally, each node stores a memory address pointing to the next node. Reversing changes these addresses to point backward. The algorithm uses three pointers to keep track of the previous node, current node, and next node to avoid losing access to the list during reversal. This pointer manipulation happens in place without creating new nodes.

Why designed this way?

This method was designed to reverse lists efficiently without extra memory or recursion overhead. Alternatives like recursion use stack space and can cause overflow on large lists. Iterative reversal is simple, fast, and safe for all list sizes.

┌─────────┐    ┌─────────┐    ┌─────────┐    ┌─────────┐
│  [1]    │ -> │  [2]    │ -> │  [3]    │ -> │  null   │
└─────────┘    └─────────┘    └─────────┘    └─────────┘

Pointer changes:
prev = null
current = [1]

After first iteration:
[1].next = null
prev = [1]
current = [2]

After second iteration:
[2].next = [1]
prev = [2]
current = [3]

After third iteration:
[3].next = [2]
prev = [3]
current = null

New head = prev = [3]

Myth Busters - 3 Common Misconceptions

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

Common Belief: You must create a new list and copy nodes to reverse a singly linked list.

Reality: Reversal can be done in place by changing pointers without creating new nodes.

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

Quick: Is recursion always better than iteration for reversing linked lists? Commit to yes or no.

Common Belief: Recursion is simpler and better for reversing linked lists.

Reality: Iterative reversal is more memory efficient and avoids stack overflow risks on large lists.

Why it matters: Using recursion blindly can cause crashes or slowdowns in real applications.

Quick: After reversal, does the original head node still point to the second node? Commit to yes or no.

Common Belief: The original head node keeps pointing forward after reversal.

Reality: The original head node's next pointer is changed to null, becoming the new tail.

Why it matters: Assuming old pointers remain can cause bugs when traversing the reversed list.

Expert Zone

1

Reversing a list in place requires careful pointer management to avoid losing access to remaining nodes.

2

The iterative method is preferred in production for its predictable memory use and speed.

3

Understanding pointer reversal helps debug complex linked list bugs like cycles or partial reversals.

When NOT to use

Avoid iterative reversal if you need to preserve the original list order or structure; instead, create a copy and reverse that. For doubly linked lists, specialized reversal methods are better. Recursive reversal can be used for educational purposes but is risky for large lists.

Production Patterns

Iterative reversal is used in undo features, reversing playback queues, and in-place data transformations. It is also a building block for more complex algorithms like reversing sublists or detecting palindromes in linked lists.

Connections

Stack Data Structure

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

Knowing how stacks reverse order helps understand the pointer flipping in linked list reversal.

Pointer Manipulation in C

Both involve changing memory addresses stored in variables to reorder data structures.

Understanding low-level pointer changes clarifies how linked list reversal works under the hood.

Undo Mechanism in Text Editors

Reversing linked lists models how undo stacks reverse user actions.

Seeing reversal as a real-world undo operation connects abstract data structure changes to everyday software features.

Common Pitfalls

#1 Losing access to the rest of the list by changing current.next before saving next.

Wrong approach:

while (current !== null) {
current.next = prev;
prev = current;
current = current.next; // current.next changed, so this is wrong
}

Correct approach:

while (current !== null) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}

Root cause:

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

#2 Returning the original head instead of the new head after reversal.

Wrong approach:

function reverseList(head) {
// reversal code
return head; // wrong, head is old start
}

Correct approach:

function reverseList(head) {
// reversal code
return prev; // prev is new head
}

Root cause:

Confusing the original head with the new head after reversal.

#3 Not handling empty list input causing errors.

Wrong approach:

function reverseList(head) {
let prev = null;
let current = head;
while (current.next !== null) { // error if head is null
// reversal steps
}
return prev;
}

Correct approach:

function reverseList(head) {
let prev = null;
let current = head;
while (current !== null) {
// reversal steps
}
return prev;
}

Root cause:

Assuming head is never null without checking causes runtime errors.

Key Takeaways

Reversing a singly linked list iteratively flips the direction of pointers in one pass without extra memory.

Using three pointers--prev, current, and next--prevents losing access to nodes during reversal.

The original head becomes the tail with its next pointer set to null after reversal.

Iterative reversal is efficient and safe for large lists compared to recursive methods.

Careful pointer management and edge case handling are essential to avoid bugs.

Practice

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

easy

A. To sort the linked list in ascending order

B. To change the direction of the links between nodes without using recursion

C. To delete all nodes from the linked list

D. To find the middle node of the linked list

Solution

1. Step 1: Understand the operation of reversing

   Reversing a singly linked list means changing the direction of the next pointers so the last node becomes the first.

2. Step 2: Identify iterative approach

   The iterative method changes links step-by-step using a loop without recursion.

3. Final Answer:

   To change the direction of the links between nodes without using recursion -> Option B

4. Quick Check:

   Reversing iteratively = changing links direction without recursion [OK]

Hint: Reversing means flipping links, not sorting or deleting [OK]

Common Mistakes:

• Confusing reversing with sorting
• Thinking recursion is required
• Assuming nodes are deleted

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

easy

A. let prev = null; let current = head;

B. let prev = head; let current = null;

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

D. let prev = null; let current = null;

Solution

1. Step 1: Understand pointer roles

   Prev starts as null because the new tail points to null; current starts at head to traverse.

2. Step 2: Match initialization

   Only let prev = null; let current = head; sets prev to null and current to head correctly for iteration.

3. Final Answer:

   let prev = null; let current = head; -> Option A

4. Quick Check:

   Prev null, current head = correct start [OK]

Hint: Prev starts null, current starts at head for iteration [OK]

Common Mistakes:

• Setting prev to head initially
• Starting current as null
• Both pointers null at start

3. Given the linked list: 1 -> 2 -> 3 -> null, what will be the output after running this iterative reversal code?

function reverseList(head: ListNode | null): ListNode | null {
  let prev = null;
  let current = head;
  while (current !== null) {
    let nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
  }
  return prev;
}

medium

A. null

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

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

D. 1 -> null

Solution

1. Step 1: Trace the reversal loop

   Initially prev=null, 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 3, which links to 2, then 1, then null.

3. Final Answer:

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

4. Quick Check:

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

Hint: Follow pointers step-by-step to see reversed links [OK]

Common Mistakes:

• Returning head instead of prev
• Not updating current correctly
• Confusing next pointer updates

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

function reverseList(head: ListNode | null): ListNode | null {
  let prev = head;
  let current = head.next;
  while (current !== null) {
    let nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
  }
  return prev;
}

medium

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

B. The function should return current instead of prev

C. nextTemp should be assigned after updating current.next

D. prev should be initialized to null, not head

Solution

1. Step 1: Check pointer initialization

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

2. Step 2: Understand impact of wrong initialization

   Starting prev at head causes a cycle or incorrect reversal.

3. Final Answer:

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

4. Quick Check:

   Prev must be null at start [OK]

Hint: Prev always null at start to avoid cycles [OK]

Common Mistakes:

• Starting prev at head causing loops
• Starting current at wrong node
• Returning wrong pointer

5. You have a singly linked list with nodes containing values: 10 -> 20 -> 30 -> 40 -> null. After reversing it iteratively, you want to insert a new node with value 25 between 20 and 30 in the reversed list. What will be the correct order of nodes after insertion?

hard

A. 40 -> 30 -> 25 -> 20 -> 10 -> null

B. 40 -> 30 -> 20 -> 25 -> 10 -> null

C. 40 -> 30 -> 20 -> 10 -> 25 -> null

D. 40 -> 25 -> 30 -> 20 -> 10 -> null

Solution

1. Step 1: Reverse the original list

   Original: 10 -> 20 -> 30 -> 40 -> null reversed becomes 40 -> 30 -> 20 -> 10 -> null.

2. Step 2: Insert 25 between 30 and 20

   In reversed list, 30 points to 20, so insert 25 after 30: 30 -> 25 -> 20.

3. Step 3: Final list order

   40 -> 30 -> 25 -> 20 -> 10 -> null.

4. Final Answer:

   40 -> 30 -> 25 -> 20 -> 10 -> null -> Option A

5. Quick Check:

   Insert between 30 and 20 in reversed list = 40->30->25->20->10 [OK]

Hint: Reverse first, then insert at correct reversed position [OK]

Common Mistakes:

• Inserting 25 between wrong nodes after reversal
• Confusing original and reversed order
• Not updating next pointers correctly