Reorder Linked List in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle node of the linked list using slow and fast pointers.

DSA C++

ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
    slow = slow->[1];
    fast = fast->next->next;
}

Drag options to blanks, or click blank then click option'

Arandom

Bprev

Cchild

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' causes the pointer to move backward.

Using 'child' or 'random' which are not standard linked list pointers.

The slow pointer moves one step at a time using next to find the middle node.

2fill in blank

medium

Complete the code to reverse the second half of the linked list starting from the middle node.

DSA C++

ListNode* prev = nullptr;
ListNode* curr = slow;
while (curr != nullptr) {
    ListNode* nextTemp = curr->next;
    curr->next = [1];
    prev = curr;
    curr = nextTemp;
}

Drag options to blanks, or click blank then click option'

Acurr

BnextTemp

Cprev

Dhead

Attempts:

3 left

💡 Hint

Common Mistakes

Setting next pointer to current or nextTemp causes cycles or loss of nodes.

Using head instead of prev breaks the reversal logic.

To reverse the list, each node's next pointer should point to the previous node.

3fill in blank

hard

Fix the error in merging the two halves of the list alternately.

DSA C++

ListNode* first = head;
ListNode* second = prev;
while (second->next != nullptr) {
    ListNode* tmp1 = first->next;
    ListNode* tmp2 = second->next;
    first->next = second;
    second->next = [1];
    first = tmp1;
    second = tmp2;
}

Drag options to blanks, or click blank then click option'

Afirst

Btmp1

Csecond

Dtmp2

Attempts:

3 left

💡 Hint

Common Mistakes

Linking second->next to tmp2 causes incorrect order.

Linking second->next to first or second causes cycles.

After linking second to first, second's next should point to the next node of first (tmp1) to maintain order.

4fill in blank

hard

Fill both blanks to correctly split the list and prepare for reversal.

DSA C++

ListNode* slow = head;
ListNode* fast = head;
while (fast != nullptr && fast->next != nullptr) {
    slow = slow->[1];
    fast = fast->next->[2];
}
slow->next = nullptr;

Drag options to blanks, or click blank then click option'

Anext

Bprev

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' causes backward movement and infinite loops.

Mixing 'next' and 'prev' breaks the logic.

Both slow and fast pointers move forward using next to find the middle and split the list.

5fill in blank

hard

Fill all three blanks to complete the reorder function that reorders the linked list as required.

DSA C++

void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->[1];
        fast = fast->next->[2];
    }
    ListNode* second = slow->next;
    slow->next = nullptr;
    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 = [3];
        first = tmp1;
        second = tmp2;
    }
}

Drag options to blanks, or click blank then click option'

Anext

Ctmp1

Dprev

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' for pointer movement.

Linking second->next incorrectly causing cycles or broken list.

The slow and fast pointers move forward using next. When merging, second's next points to tmp1 to alternate nodes.

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