Reorder Linked List in DSA C++ - Build from Scratch

Reorder Linked List

📖 Scenario: Imagine you have a line of people waiting for a show. You want to rearrange them so the first person is followed by the last person, then the second person, then the second last, and so on.

🎯 Goal: You will reorder a singly linked list so that nodes are arranged in the pattern: first node, last node, second node, second last node, and so on.

📋 What You'll Learn

Create a singly linked list with nodes containing integer values

Find the middle of the linked list

Reverse the second half of the linked list

Merge the two halves by alternating nodes

Print the reordered linked list

💡 Why This Matters

🌍 Real World

Reordering linked lists is useful in scenarios like rearranging tasks, scheduling, or organizing data streams where alternating order is needed.

💼 Career

Understanding linked list manipulation is important for software engineers working on low-level data structures, memory management, and performance optimization.

1

Create the linked list

Create a singly linked list with nodes containing these exact values in order: 1, 2, 3, 4, 5. Use the struct ListNode with int val and ListNode* next. Create a pointer head pointing to the first node.

DSA C++

// Define ListNode struct and create linked list with values 1, 2, 3, 4, 5
// Your code here

Hint

Start by defining the node structure and then link nodes one by one.

2

Find the middle of the linked list

Create two pointers slow and fast both starting at head. Move slow by one node and fast by two nodes in a loop until fast reaches the end. This will find the middle node. Store the middle node in slow.

DSA C++

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

ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);

// Find middle node using slow and fast pointers
// Your code here

Hint

Use two pointers moving at different speeds to find the middle.

3

Reverse the second half of the list

Starting from the middle node slow, reverse the linked list from there to the end. Use three pointers: prev initialized to nullptr, curr initialized to slow, and next to temporarily store the next node. Update links to reverse the list.

DSA C++

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

ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);

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

// Reverse second half starting from slow
// Your code here

Hint

Reverse the second half by changing the next pointers one by one.

4

Merge the two halves and print the reordered list

Merge the first half starting at head and the reversed second half starting at prev by alternating nodes. Use pointers first and second. After merging, print the list values separated by -> and ending with null.

DSA C++

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

ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);

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

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

// Merge two halves and print the reordered list
// Your code here

Hint

Alternate nodes from the first half and reversed second half. Then print the list.

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