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).