Why Reverse a Singly Linked List Iterative in DSA C++?

The Big Idea

What if you could flip a long chain in seconds without breaking a single link?

The Scenario

Imagine you have a long chain of paper clips linked together in a line. Now, you want to flip the entire chain so the last clip becomes the first and the first becomes the last. Doing this by hand means unhooking each clip and re-linking them backward, one by one.

The Problem

Manually flipping each clip is slow and easy to mess up. You might lose track of which clip goes next or accidentally break the chain. It takes a lot of time and careful attention, especially if the chain is very long.

The Solution

Using an iterative method to reverse a singly linked list is like having a smart helper who carefully changes the direction of each link one at a time without losing any clips. This method is fast, safe, and works no matter how long the chain is.

Before vs After

✗ Before

Node* reverseList(Node* head) {
  // Manually detach and reattach each node
  // Very complex and error-prone
}

✓ After

Node* reverseList(Node* head) {
  Node* previous = nullptr;
  Node* current = head;
  while (current != nullptr) {
    Node* nextNode = current->next;
    current->next = previous;
    previous = current;
    current = nextNode;
  }
  return previous;
}

What It Enables

This method lets you quickly flip the order of any linked list, enabling new ways to process or display data in reverse without extra space.

Real Life Example

Think of a music playlist stored as a linked list. Reversing it lets you play songs from last to first without creating a new list.

Key Takeaways

Manual reversal is slow and risky.

Iterative reversal changes links step-by-step safely.

It works efficiently for any list size.

Practice

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

easy

A. To sort the nodes in ascending order

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

C. To delete all nodes from the list

D. To create a new linked list with the same elements

Solution

1. Step 1: Understand the linked list structure

   A singly linked list has nodes connected by pointers going one way only.

2. Step 2: Purpose of iterative reversal

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

3. Final Answer:

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

4. Quick Check:

   Reversing = Changing links direction [OK]

Hint: Think of flipping arrows between nodes one at a time [OK]

Common Mistakes:

• Confusing reversal with deletion
• Thinking it sorts the list
• Assuming it creates a new list

2. Which of the following is the correct syntax to initialize the previous pointer to NULL in C++ before starting the reversal?

easy

A. Node* prev = NULL;

B. Node prev = NULL;

C. Node prev* = 0;

D. Node prev = 0;

Solution

1. Step 1: Understand pointer initialization

   In C++, pointers are declared with * and can be set to NULL or nullptr.

2. Step 2: Correct pointer declaration

   "Node* prev = NULL;" correctly declares a pointer named prev and initializes it to NULL.

3. Final Answer:

   Node* prev = NULL; -> Option A

4. Quick Check:

   Pointer prev initialized to NULL [OK]

Hint: Use * for pointers and assign NULL or nullptr [OK]

Common Mistakes:

• Declaring pointer without *
• Assigning NULL to non-pointer variable
• Using 0 without pointer declaration

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

medium

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

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

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

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

Solution

1. Step 1: Trace reversal of 1 -> 2 -> 3

   Start with prev = NULL, curr = 1. Change 1's next to NULL, move prev to 1, curr to 2.

2. Step 2: Continue reversing links

   Change 2's next to 1, move prev to 2, curr to 3. Then change 3's next to 2, prev to 3, curr to NULL.

3. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

4. Quick Check:

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

Hint: Reverse pointers one by one from head to tail [OK]

Common Mistakes:

• Not updating pointers correctly
• Leaving last node pointing to old next
• Confusing original and reversed order

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

Node* reverse(Node* head) {
  Node* prev = NULL;
  Node* curr = head;
  while (curr != NULL) {
    Node* next = curr->next;
    curr->next = prev;
    prev = curr;
    // Missing update of curr here
  }
  return prev;
}

medium

A. prev is not initialized to NULL

B. The function returns head instead of prev

C. next pointer is not declared

D. The pointer curr is never updated inside the loop, causing an infinite loop

Solution

1. Step 1: Check loop pointer updates

   Inside the loop, curr must move to next node to avoid infinite loop.

2. Step 2: Identify missing update

   The code misses 'curr = next;' causing curr to never change and loop forever.

3. Final Answer:

   The pointer curr is never updated inside the loop, causing an infinite loop -> Option D

4. Quick Check:

   Missing curr update = infinite loop [OK]

Hint: Always move current pointer forward inside the loop [OK]

Common Mistakes:

• Forgetting to update curr
• Returning wrong pointer
• Not initializing prev

5. Given a singly linked list with nodes containing values [10, 20, 30, 40, 50], which of the following code snippets correctly reverses the list iteratively and returns the new head?

hard

A. Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr != nullptr) { curr->next = prev; prev = curr; } return prev; }

B. Node* reverseList(Node* head) { Node* curr = head; Node* prev = nullptr; while (prev) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return curr; }

C. Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; }

D. Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr != nullptr) { Node* next = curr->next; prev = curr; curr = next; } return prev; }

Solution

1. Step 1: Check pointer initialization and loop condition

   Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } initializes prev to nullptr, curr to head, and loops while curr is not null.

2. Step 2: Verify pointer updates inside loop

   Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } saves next, reverses curr->next, moves prev and curr forward correctly, then returns prev as new head.

3. Final Answer:

   Node* reverseList(Node* head) { Node* prev = nullptr; Node* curr = head; while (curr) { Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } -> Option C

4. Quick Check:

   Correct pointer updates and return [OK]

Hint: Save next, reverse link, move prev and curr forward [OK]

Common Mistakes:

• Wrong loop condition
• Not saving next before changing links
• Returning wrong pointer