Reorder Linked List in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Reorder Linked List Function

What is the printed linked list after running the reorder function on the list 1 -> 2 -> 3 -> 4 -> 5 -> null?

DSA C

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

void reorderList(Node* head) {
    if (!head || !head->next) return;
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Node* prev = NULL;
    Node* curr = slow->next;
    slow->next = NULL;
    while (curr) {
        Node* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    Node* first = head;
    Node* second = prev;
    while (second) {
        Node* tmp1 = first->next;
        Node* tmp2 = second->next;
        first->next = second;
        second->next = tmp1;
        first = tmp1;
        second = tmp2;
    }
}

// After reorderList, print list from head to null
// Expected output format: "1 -> 5 -> 2 -> 4 -> 3 -> null"

A 1 -> 3 -> 2 -> 5 -> 4 -> null

B 1 -> 4 -> 2 -> 5 -> 3 -> null

C 1 -> 2 -> 3 -> 4 -> 5 -> null

D 1 -> 5 -> 2 -> 4 -> 3 -> null

💡 Hint

Think about splitting the list into two halves, reversing the second half, then merging alternately.

The reorderList function splits the list into two halves, reverses the second half, then merges nodes alternately from the first and reversed second half. For input 1->2->3->4->5, the reordered list is 1->5->2->4->3->null.

🧠 Conceptual

intermediate

Understanding the Purpose of Slow and Fast Pointers

In the reorder linked list algorithm, what is the main purpose of using slow and fast pointers?

A To find the middle node of the linked list efficiently

B To reverse the linked list in place

C To merge two linked lists alternately

D To detect if the linked list has a cycle

💡 Hint

Slow moves one step, fast moves two steps.

Slow and fast pointers are used to find the middle of the list by moving at different speeds. When fast reaches the end, slow is at the middle.

🔧 Debug

advanced

Identify the Bug in Reversing the Second Half

Given the following code snippet to reverse the second half of a linked list, what is the bug that causes incorrect reversal?

DSA C

Node* prev = NULL;
Node* curr = slow->next;
slow->next = NULL;
while (curr) {
    Node* nextTemp = curr->next;
    curr->next = prev;
    prev = curr;
    // Missing update of curr here
}
// prev should be the head of reversed list

A The 'slow->next' should not be set to NULL before reversal

B The pointer 'prev' is not initialized to NULL

C The pointer 'curr' is not updated inside the loop, causing an infinite loop

D The reversal logic is correct; no bug present

💡 Hint

Check if the loop moves forward properly.

Inside the while loop, 'curr' must be updated to 'nextTemp' to move forward. Missing this causes infinite loop.

🚀 Application

advanced

Reordering an Even Length Linked List

What is the reordered linked list after applying the reorderList function on 10 -> 20 -> 30 -> 40 -> null?

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

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

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

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

💡 Hint

Split the list, reverse second half, then merge alternately.

For even length list, the middle is between 20 and 30. After reversal and merging, the list becomes 10->40->20->30->null.

📝 Syntax

expert

Correct Order of Steps in Reorder Linked List Algorithm

Select the correct sequence of steps to reorder a linked list as per the standard algorithm.

A 2,1,3,4

B 1,3,2,4

C 1,2,3,4

D 3,1,2,4

💡 Hint

Think about finding middle first, then splitting, then reversing second half.

First find middle (1), then split list into two halves (3), reverse second half (2), then merge (4).

Practice

1. What is the main goal of the Reorder Linked List operation?

easy

A. To rearrange the list so nodes alternate from start and end

B. To sort the linked list in ascending order

C. To reverse the entire linked list

D. To remove duplicate nodes from the list

Solution

1. Step 1: Understand the reorder pattern

   The reorder linked list operation rearranges nodes so that the first node is followed by the last node, then the second node, then the second last node, and so on.

2. Step 2: Differentiate from other operations

   This is different from sorting, reversing, or removing duplicates because it mixes nodes from start and end alternatively.

3. Final Answer:

   To rearrange the list so nodes alternate from start and end -> Option A

4. Quick Check:

   Reorder = alternate start and end nodes [OK]

Hint: Reorder means alternate nodes from front and back [OK]

Common Mistakes:

• Confusing reorder with sorting
• Thinking reorder means reversing the list
• Assuming reorder removes duplicates

2. Which of the following C code snippets correctly finds the middle node of a singly linked list for reordering?

easy

A. while (fast && fast->next) { fast = fast->next; slow = slow->next; }

B. while (slow && slow->next) { fast = fast->next; slow = slow->next->next; }

C. while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }

D. while (fast && slow) { slow = slow->next->next; fast = fast->next->next; }

Solution

1. Step 1: Identify the fast and slow pointer technique

   To find the middle node, fast pointer moves two steps, slow pointer moves one step until fast reaches end.

2. Step 2: Check each option for correct pointer movement

   while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } correctly moves fast by two and slow by one. Others have incorrect pointer movements causing errors or wrong middle.

3. Final Answer:

   while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } -> Option C

4. Quick Check:

   Fast moves 2 steps, slow moves 1 step [OK]

Hint: Fast pointer moves twice as fast as slow pointer [OK]

Common Mistakes:

• Swapping fast and slow pointer movements
• Not checking fast->next before fast->next->next
• Using slow pointer to move two steps

3. Given the linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, what is the reordered list after applying the reorder operation?

medium

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

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

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

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

Solution

1. Step 1: Identify the reorder pattern on the list

   The reorder pattern takes first node, last node, second node, second last node, and so on.

2. Step 2: Apply pattern to given list

   Start with 1, then 5, then 2, then 4, then 3. So reordered list is 1 -> 5 -> 2 -> 4 -> 3 -> NULL.

3. Final Answer:

   1 -> 5 -> 2 -> 4 -> 3 -> NULL -> Option D

4. Quick Check:

   Alternate front and back nodes [OK]

Hint: Alternate nodes from start and end [OK]

Common Mistakes:

• Reversing the entire list instead
• Keeping original order unchanged
• Skipping nodes or mixing order

4. Consider this buggy C code snippet for reordering a linked list. What is the main error?

void reorderList(Node* head) {
  Node *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next;
  }
  // further code omitted
}

medium

A. Fast pointer moves only one step instead of two

B. Slow pointer moves two steps instead of one

C. Missing check for head being NULL

D. Using wrong variable names for pointers

Solution

1. Step 1: Analyze pointer movements in the loop

   Fast pointer should move two steps to find middle, but here it moves only one step.

2. Step 2: Identify impact of incorrect fast pointer movement

   This causes slow pointer to not reach the true middle, breaking reorder logic.

3. Final Answer:

   Fast pointer moves only one step instead of two -> Option A

4. Quick Check:

   Fast must move 2 steps, not 1 [OK]

Hint: Fast pointer moves twice as fast as slow [OK]

Common Mistakes:

• Not moving fast pointer two steps
• Ignoring NULL checks
• Confusing slow and fast pointer roles

5. You have a linked list: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULL. After reordering, what will be the list? Also, explain why the middle node is chosen as it is.

hard

A. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 40 because it's the node after center

B. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 30 because it's the exact center for even length

C. 10 -> 50 -> 20 -> 40 -> 30 -> 60 -> NULL; middle is 30 because it's the exact center

D. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 20 because it's the first half's end

Solution

1. Step 1: Find the middle node for even length list

   For 6 nodes, middle is node 3 (value 30) because slow pointer stops at exact center when fast moves two steps.

2. Step 2: Apply reorder pattern

   Reorder alternates nodes from start and end: 10, 60, 20, 50, 30, 40.

3. Final Answer:

   10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 30 because it's the exact center for even length -> Option B

4. Quick Check:

   Middle at center, reorder alternates front and back [OK]

Hint: Middle is center node; reorder alternates front and back [OK]

Common Mistakes:

• Choosing wrong middle for even length
• Mixing reorder order
• Confusing node positions