Reorder Linked List in DSA C++

Mental Model

We rearrange the list so nodes alternate from start and end, meeting in the middle.

Analogy: Imagine lining up people from two ends of a queue, taking one from the front, then one from the back, repeating until all are rearranged.

1 -> 2 -> 3 -> 4 -> 5 -> null
↑start pointer

Dry Run Walkthrough

Input: list: 1->2->3->4->5

Goal: Rearrange list to 1->5->2->4->3

Step 1: Find middle node using slow and fast pointers

1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑slow, ↑fast

Why: We need to split the list into two halves at the middle

Step 2: Split list into two halves: first half 1->2->3, second half 4->5

First half: 1 -> 2 -> 3 -> null
Second half: 4 -> 5 -> null

Why: Separating halves allows reversing the second half

Step 3: Reverse second half: 4 -> 5 becomes 5 -> 4

First half: 1 -> 2 -> 3 -> null
Reversed second half: 5 -> 4 -> null

Why: Reversing second half prepares for alternating merge

Step 4: Merge nodes alternately from first and reversed second half

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

Why: Alternating nodes from front and back achieves the reorder

Result:

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

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;

        // Find middle of list
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next; // advance slow by 1
            fast = fast->next->next; // advance fast by 2
        }

        // Split and reverse second half
        ListNode* second = slow->next;
        slow->next = nullptr; // break list
        second = reverseList(second);

        // Merge two halves
        ListNode* first = head;
        while (second) {
            ListNode* tmp1 = first->next;
            ListNode* tmp2 = second->next;

            first->next = second; // link first to second
            second->next = tmp1; // link second to next of first

            first = tmp1; // move first forward
            second = tmp2; // move second forward
        }
    }

private:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev; // reverse pointer
            prev = curr; // move prev forward
            curr = nextTemp; // move curr forward
        }
        return prev;
    }
};

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

int main() {
    // Create list 1->2->3->4->5
    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);

    Solution sol;
    sol.reorderList(head);

    printList(head);
    return 0;
}

while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; }

Find middle node by advancing slow by 1 and fast by 2

slow->next = nullptr;

Split list into two halves by breaking link at middle

second = reverseList(second);

Reverse second half of the list

while (second) { ListNode* tmp1 = first->next; ListNode* tmp2 = second->next; first->next = second; second->next = tmp1; first = tmp1; second = tmp2; }

Merge nodes alternately from first and reversed second half

curr->next = prev;

Reverse pointer direction in second half

Output

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

Complexity Analysis

Time: O(n) because we traverse the list multiple times but each node is processed a constant number of times

Space: O(1) because we reorder the list in place without extra data structures

vs Alternative: Naive approach might use extra arrays to reorder, costing O(n) extra space, while this uses constant space

Edge Cases

empty list

function returns immediately without changes

DSA C++

if (!head || !head->next) return;

single node list

function returns immediately without changes

DSA C++

if (!head || !head->next) return;

two node list

list remains the same as reorder does not change order

DSA C++

while (fast->next && fast->next->next)

When to Use This Pattern

When asked to reorder a linked list alternating nodes from front and back, use the reorder list pattern by splitting, reversing second half, and merging.

Common Mistakes

Mistake: Not breaking the list at the middle causing cycles or incorrect merges
Fix: Set slow->next = nullptr to split the list cleanly

Mistake: Merging without saving next pointers causing lost nodes
Fix: Save next pointers before re-linking nodes during merge

Summary

Rearranges a linked list so nodes alternate from start and end towards the middle.

Use when you need to reorder a list in a specific alternating pattern without extra space.

The key is to find the middle, reverse the second half, then merge nodes alternately.

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