Reorder Linked List in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

To rearrange the nodes of a singly linked list so that the list changes from L0 → L1 → ... → Ln-1 → Ln to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... without creating new nodes.

intermediate

Which three main steps are used to solve the Reorder Linked List problem efficiently?

1. Find the middle of the linked list.
2. Reverse the second half of the list.
3. Merge the two halves by alternating nodes.

beginner

How do you find the middle node of a singly linked list?

Use two pointers: a slow pointer moves one step at a time, and a fast pointer moves two steps at a time. When the fast pointer reaches the end, the slow pointer is at the middle.

intermediate

What is the purpose of reversing the second half of the linked list in the reorder process?

Reversing the second half allows easy merging from the end towards the middle, so nodes can be alternated from the front and back in the desired order.

intermediate

What is the time complexity of the reorder linked list algorithm using the three-step approach?

The time complexity is O(n) because each step (finding middle, reversing, merging) processes the list nodes at most once.

What technique is used to find the middle of a linked list?

A Counting nodes and dividing by two

B Two pointers: slow and fast

C Using a stack

D Recursion

The two-pointer technique uses a slow pointer moving one step and a fast pointer moving two steps to find the middle efficiently.

Why do we reverse the second half of the linked list in the reorder process?

A To prepare for merging nodes from the end

B To find the middle node

C To delete duplicate nodes

D To sort the list

Reversing the second half allows merging nodes alternately from front and back.

What is the final order of nodes after reordering a list 1 → 2 → 3 → 4 → 5?

A 3 → 2 → 1 → 4 → 5

B 5 → 4 → 3 → 2 → 1

C 1 → 2 → 3 → 4 → 5

D 1 → 5 → 2 → 4 → 3

The reordered list alternates nodes from start and end: 1, then 5, then 2, then 4, then 3.

What is the space complexity of the reorder linked list algorithm?

A O(1)

B O(log n)

C O(n)

D O(n^2)

The algorithm rearranges nodes in place without extra data structures, so space complexity is O(1).

Which of these is NOT a step in the reorder linked list algorithm?

A Find the middle node

B Reverse the second half

C Sort the entire list

D Merge two halves alternately

Sorting the entire list is not part of the reorder linked list algorithm.

Explain the three main steps to reorder a singly linked list in the required pattern.

Think about splitting, reversing, and merging.

Describe how the two-pointer technique helps in the reorder linked list problem.

Focus on how to find the middle efficiently.

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