Reverse a Singly Linked List Iterative in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of reversing a linked list with 3 nodes

What is the printed output of the linked list after reversing it iteratively?

DSA C

typedef struct Node {
    int data;
    struct Node* next;
} Node;

#include <stdio.h>
#include <stdlib.h>

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

void printList(Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = malloc(sizeof(Node));
    head->data = 1;
    head->next = malloc(sizeof(Node));
    head->next->data = 2;
    head->next->next = malloc(sizeof(Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;

    head = reverseList(head);
    printList(head);
    return 0;
}

A 3 -> 1 -> 2 -> NULL

B 1 -> 2 -> 3 -> NULL

C NULL

D 3 -> 2 -> 1 -> NULL

💡 Hint

Think about how the pointers change direction in the iterative reversal.

The iterative reversal changes the next pointers of each node to point to the previous node, reversing the list order from 1->2->3 to 3->2->1.

❓ Predict Output

intermediate

Output after reversing a single-node linked list

What is the output when reversing a linked list with only one node?

DSA C

typedef struct Node {
    int data;
    struct Node* next;
} Node;

#include <stdio.h>
#include <stdlib.h>

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

void printList(Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    Node* head = malloc(sizeof(Node));
    head->data = 42;
    head->next = NULL;

    head = reverseList(head);
    printList(head);
    return 0;
}

A 42 -> 42 -> NULL

B NULL

C 42 -> NULL

D Error: segmentation fault

💡 Hint

Reversing a single node list should not change the list.

A single node points to NULL, so reversing it keeps the same node as head.

❓ Predict Output

advanced

Output of reversing a linked list with a cycle

What happens when you run the iterative reverse function on a linked list that contains a cycle?

DSA C

typedef struct Node {
    int data;
    struct Node* next;
} Node;

#include <stdio.h>
#include <stdlib.h>

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

int main() {
    Node* head = malloc(sizeof(Node));
    Node* second = malloc(sizeof(Node));
    Node* third = malloc(sizeof(Node));
    head->data = 1;
    head->next = second;
    second->data = 2;
    second->next = third;
    third->data = 3;
    third->next = second; // cycle here

    head = reverseList(head);
    printf("Reversed list printed\n");
    return 0;
}

A Program runs infinitely (infinite loop)

B NULL

C 3 -> 2 -> 1 -> NULL

D Segmentation fault error

💡 Hint

Think about what happens when the list has a cycle and the loop condition depends on current != NULL.

The reversal loop never ends because current never becomes NULL due to the cycle, causing an infinite loop.

❓ Predict Output

advanced

Final state of pointers after one iteration of reversal

Given the initial linked list 1 -> 2 -> 3 -> NULL, what are the values of prev, current, and next pointers after the first iteration of the reversal loop?

DSA C

typedef struct Node {
    int data;
    struct Node* next;
} Node;

#include <stdio.h>
#include <stdlib.h>

int main() {
    Node* head = malloc(sizeof(Node));
    head->data = 1;
    head->next = malloc(sizeof(Node));
    head->next->data = 2;
    head->next->next = malloc(sizeof(Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;

    Node* prev = NULL;
    Node* current = head;
    Node* next = NULL;

    // First iteration of reversal loop
    next = current->next;
    current->next = prev;
    prev = current;
    current = next;

    printf("prev: %d, current: %d, next: %d\n", prev->data, current->data, next->data);
    return 0;
}

A prev: NULL, current: 1, next: 2

B prev: 1, current: 2, next: 2

C prev: 2, current: 3, next: 3

D prev: 1, current: 3, next: 3

💡 Hint

Trace the pointer changes step by step for the first iteration.

After first iteration, prev points to node with data 1, current and next point to node with data 2.

🧠 Conceptual

expert

Why iterative reversal is preferred over recursive for large lists

Which is the main reason iterative reversal of a singly linked list is preferred over recursive reversal for very large lists?

A Recursive reversal uses extra stack space which can cause stack overflow for large lists

B Iterative reversal is slower than recursive reversal for large lists

C Recursive reversal cannot reverse lists with cycles

D Iterative reversal requires more memory than recursive reversal

💡 Hint

Think about how recursion uses memory for each function call.

Recursive reversal uses function call stack for each node, which can overflow for large lists. Iterative reversal uses constant extra space.

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