Reorder Linked List in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Reordering a Linked List

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

DSA C++

struct Node {
    int val;
    Node* next;
    Node(int x) : val(x), next(nullptr) {}
};

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

void printList(Node* head) {
    while (head) {
        std::cout << head->val;
        if (head->next) std::cout << " -> ";
        head = head->next;
    }
    std::cout << " -> null" << std::endl;
}

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    reorderList(head);
    printList(head);
    return 0;
}

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

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

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

D 1 -> 3 -> 2 -> 5 -> 4 -> 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 at the middle, reverses the second half, then merges nodes alternately from the first and reversed second half. For the list 1->2->3->4->5, the reordered list is 1->5->2->4->3.

🧠 Conceptual

intermediate

Understanding the Reorder Linked List Algorithm

Which step is NOT part of the standard approach to reorder a linked list as per the common algorithm?

A Find the middle of the list using slow and fast pointers

B Reverse the second half of the list

C Sort the entire list in ascending order

D Merge the two halves by alternating nodes

💡 Hint

Reordering does not involve sorting the list.

The reorder linked list algorithm involves finding the middle, reversing the second half, and merging alternately. Sorting the list is not part of this algorithm.

🔧 Debug

advanced

Identify the Error in Reorder List Implementation

What error will this code produce when trying to reorder the list 1 -> 2 -> 3 -> 4 -> null? Code snippet: void reorderList(Node* head) { if (!head) return; Node* slow = head; Node* fast = head->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } Node* second = slow->next; slow->next = nullptr; Node* prev = nullptr; while (second) { Node* tmp = second->next; second->next = prev; prev = second; second = tmp; } Node* first = head; second = prev; while (second) { Node* tmp1 = first->next; Node* tmp2 = second->next; first->next = second; second->next = tmp1; first = tmp1; second = tmp2; } }

A Segmentation fault due to null pointer dereference

B No error, code runs correctly

C Infinite loop in merging step

D Compilation error due to missing return type

💡 Hint

Check how fast pointer is initialized and used in the while loop.

Initializing fast to head->next causes the while loop to skip the middle node incorrectly for even length lists, leading to incorrect splitting and possible null pointer dereference during merging.

📝 Syntax

advanced

Correct the Syntax Error in Reorder List Code

Which option fixes the syntax error in this snippet? Code snippet: Node* prev = nullptr while (second) { Node* tmp = second->next; second->next = prev; prev = second; second = tmp; }

A Change 'Node* tmp = second->next;' to 'auto tmp = second->next;'

B Add a semicolon after 'Node* prev = nullptr;'

C Add braces around the while loop body

D Replace 'nullptr' with 'NULL' and add semicolon

💡 Hint

Check the line before the while loop for missing punctuation.

The line 'Node* prev = nullptr' is missing a semicolon, causing a syntax error. Adding the semicolon fixes the syntax error.

🚀 Application

expert

Final Order of Nodes After Reordering

Given the linked list 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null, what is the order of nodes after applying the reorder list algorithm?

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

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

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

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

💡 Hint

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

The list splits into 10->20->30 and 40->50->60. Reversing second half gives 60->50->40. Merging alternately results in 10->60->20->50->30->40.

Practice

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

easy

A. Rearrange the list so nodes alternate from start and end towards the center

B. Sort the linked list in ascending order

C. Reverse the entire linked list

D. Remove duplicate nodes from the list

Solution

1. Step 1: Understand the problem statement

   The problem asks to reorder the linked list so that nodes are taken alternately from the start and the end, moving towards the center.

2. Step 2: Differentiate from other operations

   This is not sorting or reversing the entire list, but a specific rearrangement pattern.

3. Final Answer:

   Rearrange the list so nodes alternate from start and end towards the center -> Option A

4. Quick Check:

   Reorder Linked List = Alternate nodes from start and end [OK]

Hint: Think of weaving nodes from front and back alternately [OK]

Common Mistakes:

• Confusing reorder with sorting
• Trying to reverse the whole list instead
• Ignoring the alternating pattern

2. Which of the following C++ code snippets correctly declares a singly linked list node for the reorder linked list problem?

easy

A. struct ListNode { int val; ListNode* next; ListNode(int x) : val(x) {} };

B. class ListNode { int val; ListNode* next; ListNode(int x) { val = x; next = NULL; } };

C. class ListNode { public: int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };

D. struct ListNode { int val; ListNode* next; ListNode() { val = 0; next = NULL; } };

Solution

1. Step 1: Check access specifiers and constructor

   class ListNode { public: int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; uses class with public members and a constructor initializing val and next properly.

2. Step 2: Identify issues in other options

   A doesn't initialize next. B misses public (members and constructor private by default). C has default constructor but no parameterized one.

3. Final Answer:

   class ListNode with public members and parameterized constructor -> Option C

4. Quick Check:

   Proper class with public and constructor = class ListNode { public: int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; [OK]

Hint: Use public members and constructor initialization list [OK]

Common Mistakes:

• Missing public keyword in class
• Not initializing next pointer
• Using struct without constructor

3. What will be the reordered linked list after applying the reorder algorithm on the list: 1 -> 2 -> 3 -> 4 -> 5 -> null?

medium

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

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

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

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

Solution

1. Step 1: Identify the reorder pattern

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

2. Step 2: Apply pattern to given list

   Start with 1, then 5, then 2, then 4, then 3 in the middle.

3. Final Answer:

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

4. Quick Check:

   Alternate front and back nodes = 1 -> 5 -> 2 -> 4 -> 3 -> null [OK]

Hint: Pick nodes alternately from front and back [OK]

Common Mistakes:

• Reversing entire list instead
• Not alternating nodes correctly
• Leaving list unchanged

4. Given the following code snippet for reordering a linked list, what is the main bug causing incorrect output?

void reorderList(ListNode* head) {
  if (!head) return;
  ListNode* slow = head;
  ListNode* fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
  }
  ListNode* second = slow;
  ListNode* prev = nullptr;
  while (second) {
    ListNode* tmp = second->next;
    second->next = prev;
    prev = second;
    second = tmp;
  }
  ListNode* first = head;
  second = prev;
  while (second) {
    ListNode* tmp1 = first->next;
    ListNode* tmp2 = second->next;
    first->next = second;
    second->next = tmp1;
    first = tmp1;
    second = tmp2;
  }
}

medium

A. The list is not checked for empty before processing

B. The fast pointer initialization is incorrect

C. The middle node is included in the reversed second half causing cycle

D. The merging loop condition should be while (second->next) not while (second)

Solution

1. Step 1: Analyze the merging loop condition

   The merging loop uses while (second), which processes one extra node causing cycle or incorrect linking.

2. Step 2: Correct loop condition

   Changing it to while (second->next) ensures all nodes from the second half are merged properly without overlap.

3. Final Answer:

   The merging loop condition should be while (second->next) not while (second) -> Option D

4. Quick Check:

   Loop condition must stop before the last overlapping node [OK]

Hint: Use while(second->next) to merge without cycle [OK]

Common Mistakes:

• Using while(second) creates cycle
• Not reversing second half correctly
• Not handling empty list

5. You have a linked list with nodes: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null. After applying the reorder linked list algorithm, what will be the final list?

hard

A. 60 -> 50 -> 40 -> 30 -> 20 -> 10 -> null

B. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> null

C. 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> null

D. 10 -> 30 -> 50 -> 60 -> 40 -> 20 -> null

Solution

1. Step 1: Identify the reorder pattern

   The reorder pattern takes nodes alternately from the front and back: first node, last node, second node, second last node, and so on.

2. Step 2: Apply pattern to given list

   Start with 10, then 60, then 20, then 50, then 30, then 40.

3. Final Answer:

   10 -> 60 -> 20 -> 50 -> 30 -> 40 -> null -> Option B

4. Quick Check:

   Alternate front and back nodes = 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> null [OK]

Hint: Alternate nodes from front and back until center [OK]

Common Mistakes:

• Reversing entire list instead
• Not alternating nodes properly
• Leaving list unchanged