Reverse a Singly Linked List Iterative in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind reversing a singly linked list iteratively?

We change the direction of each node's pointer one by one, so the list points backward instead of forward.

beginner

In the iterative reversal of a singly linked list, which pointers do we typically use?

We use three pointers: previous (starts as NULL), current (starts at head), and next (to store current's next node).

beginner

Why do we need to store the next node before changing the current node's pointer?

Because once we change the current node's pointer to previous, we lose the original next node. Storing it first lets us continue traversing the list.

beginner

What is the time complexity of reversing a singly linked list iteratively?

It is O(n), where n is the number of nodes, because we visit each node exactly once.

beginner

Show the final state of the list after reversing: 1 -> 2 -> 3 -> NULL

After reversal, the list becomes: 3 -> 2 -> 1 -> NULL

Which pointer should initially be set to NULL when reversing a singly linked list iteratively?

A previous

B current

C next

D head

The previous pointer starts as NULL because the new tail node will point to NULL after reversal.

What do we do after changing the current node's next pointer to previous?

A Move current to previous, and next to current

B Move next to previous, and current to next

C Move previous to current, and current to next

D Stop the process

We move previous to current and current to next to continue reversing the list step by step.

What happens if we forget to store the next node before changing pointers?

A We lose access to the rest of the list

B The list reverses correctly

C The list becomes circular

D Nothing changes

Without storing next, we lose the link to the rest of the list and cannot continue traversal.

What is the new head of the list after iterative reversal?

A NULL

B The original head node

C The middle node

D The original tail node

After reversal, the original tail becomes the new head.

What is the space complexity of iterative reversal of a singly linked list?

A O(n)

B O(1)

C O(log n)

D O(n^2)

We only use a few pointers, so space complexity is constant O(1).

Explain step-by-step how to reverse a singly linked list using iteration.

Think about how pointers move and change direction one by one.

Describe why reversing a singly linked list iteratively is efficient in terms of time and space.

Focus on how many times nodes are visited and how much memory is used.

Practice

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

easy

A. To delete all nodes from the linked list

B. To create a new linked list with reversed elements

C. To sort the linked list in ascending 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 connected in one direction only, from head to tail.

2. Step 2: Purpose of iterative reversal

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

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 reversal creates a new list instead of changing links
• Confusing reversal with sorting
• Assuming nodes are deleted during reversal

2. Which of the following is the correct way to initialize pointers for iterative reversal of a singly linked list in C?

easy

A. struct Node *prev = NULL, *current = head, *next = NULL;

B. struct Node *prev = head, *current = NULL, *next = NULL;

C. struct Node *prev = NULL, *current = NULL, *next = head;

D. struct Node *prev = head, *current = head, *next = head;

Solution

1. Step 1: Identify starting pointers

   For reversal, prev starts as NULL because the new tail points to NULL, current starts at head to traverse.

2. Step 2: Correct initialization

   Next pointer is initialized as NULL and updated inside the loop; so initial next = NULL is correct.

3. Final Answer:

   struct Node *prev = NULL, *current = head, *next = NULL; -> Option A

4. Quick Check:

   Prev NULL, current head to start [OK]

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

Common Mistakes:

• Setting prev to head initially
• Setting current to NULL at start
• Initializing next pointer incorrectly

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

medium

A. 2 -> 3 -> 1 -> NULL

B. 3 -> 2 -> 1 -> NULL

C. NULL -> 3 -> 2 -> 1

D. 1 -> 2 -> 3 -> NULL

Solution

1. Step 1: Trace reversal process

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

2. Step 2: Confirm final head

   The last node (3) becomes the new head, so output is 3->2->1->NULL.

3. Final Answer:

   3 -> 2 -> 1 -> NULL -> Option B

4. Quick Check:

   Reverse order of nodes [OK]

Hint: Reverse means last becomes first [OK]

Common Mistakes:

• Assuming list stays the same after reversal
• Confusing NULL placement
• Mixing node order incorrectly

4. Identify the error in this iterative reversal code snippet for a singly linked list in C:

struct Node* reverse(struct Node* head) {
  struct Node* prev = head;
  struct Node* current = head;
  struct Node* next = NULL;
  while (current != NULL) {
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

medium

A. prev should be initialized to NULL, not head

B. current should be initialized to NULL, not head

C. next pointer is not updated inside the loop

D. Function should return current, not prev

Solution

1. Step 1: Check pointer initialization

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

2. Step 2: Analyze loop pointer updates

   Current and next are correctly updated; only prev initialization is wrong.

3. Final Answer:

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

4. Quick Check:

   Prev NULL to mark new tail [OK]

Hint: Prev must start NULL to avoid cycle [OK]

Common Mistakes:

• Starting prev at head causing cycle
• Not updating next inside loop
• Returning wrong pointer at end

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

hard

A. NULL

B. 40 -> 30 -> 20 -> 10 -> NULL

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

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

Solution

1. Step 1: Reverse the list once

   Original: 10->20->30->40->NULL. After first reversal: 40->30->20->10->NULL.

2. Step 2: Reverse the reversed list again

   Reversing 40->30->20->10->NULL returns it to original: 10->20->30->40->NULL.

3. Final Answer:

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

4. Quick Check:

   Double reversal restores original list [OK]

Hint: Reversing twice returns original list [OK]

Common Mistakes:

• Assuming double reversal changes list order
• Confusing node values after reversal
• Forgetting NULL at list end