Reorder Linked List in DSA C

Mental Model

We rearrange the list so nodes alternate from start and end towards the center.

Analogy: Imagine lining up people from two ends of a line and making them walk towards the middle, alternating one from the front, then one from the back.

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

Dry Run Walkthrough

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

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

Step 1: Find middle node using slow and fast pointers

1 -> 2 -> 3 -> 4 -> 5 -> null
          ↑middle at 3

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

Step 2: Reverse second half starting from node after middle

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

Why: Reversing second half helps to alternate nodes from front and back

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

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 <stdio.h>
#include <stdlib.h>

// Define node structure
typedef struct Node {
    int val;
    struct Node* next;
} Node;

// Create new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    return node;
}

// Print linked list
void printList(Node* head) {
    Node* curr = head;
    while (curr) {
        printf("%d", curr->val);
        if (curr->next) printf(" -> ");
        curr = curr->next;
    }
    printf(" -> null\n");
}

// Reverse linked list
Node* reverseList(Node* head) {
    Node* prev = NULL;
    Node* curr = head;
    while (curr) {
        Node* nextTemp = curr->next; // save next
        curr->next = prev;           // reverse pointer
        prev = curr;                 // move prev forward
        curr = nextTemp;             // move curr forward
    }
    return prev; // new head
}

// Reorder list function
void reorderList(Node* head) {
    if (!head || !head->next) return; // empty or single node

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

    // 2. Reverse second half
    Node* second = reverseList(slow->next);
    slow->next = NULL; // split list

    // 3. Merge two halves
    Node* first = head;
    while (second) {
        Node* tmp1 = first->next;   // save next of first
        Node* tmp2 = second->next;  // save next of second

        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
    }
}

int main() {
    // Create list 1->2->3->4->5->null
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    reorderList(head);
    printList(head);

    return 0;
}

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

advance slow and fast pointers to find middle node

Node* second = reverseList(slow->next); slow->next = NULL;

reverse second half and split list into two

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

merge nodes from first and second halves alternately

Output

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

Complexity Analysis

Time: O(n) because we traverse the list multiple times but each node is visited 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) space, but this method uses pointers only

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;

list with two nodes

reordering does nothing as list is already in order

DSA C

while (fast->next && fast->next->next) { ... }

When to Use This Pattern

When you need 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 splitting the list after finding the middle, causing cycles or incorrect merges
Fix: Set slow->next = NULL after reversing second half to split the list

Mistake: Not reversing the second half before merging, leading to wrong order
Fix: Reverse the second half before merging to alternate nodes correctly

Summary

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

Use when you want to reorder a list to alternate nodes from front and back without extra space.

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

Practice

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

easy

A. To rearrange the list so nodes alternate from start and end

B. To sort the linked list in ascending order

C. To reverse the entire linked list

D. To remove duplicate nodes from the list

Solution

1. Step 1: Understand the reorder pattern

   The reorder linked list operation rearranges nodes so that the first node is followed by the last node, then the second node, then the second last node, and so on.

2. Step 2: Differentiate from other operations

   This is different from sorting, reversing, or removing duplicates because it mixes nodes from start and end alternatively.

3. Final Answer:

   To rearrange the list so nodes alternate from start and end -> Option A

4. Quick Check:

   Reorder = alternate start and end nodes [OK]

Hint: Reorder means alternate nodes from front and back [OK]

Common Mistakes:

• Confusing reorder with sorting
• Thinking reorder means reversing the list
• Assuming reorder removes duplicates

2. Which of the following C code snippets correctly finds the middle node of a singly linked list for reordering?

easy

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

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

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

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

Solution

1. Step 1: Identify the fast and slow pointer technique

   To find the middle node, fast pointer moves two steps, slow pointer moves one step until fast reaches end.

2. Step 2: Check each option for correct pointer movement

   while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } correctly moves fast by two and slow by one. Others have incorrect pointer movements causing errors or wrong middle.

3. Final Answer:

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

4. Quick Check:

   Fast moves 2 steps, slow moves 1 step [OK]

Hint: Fast pointer moves twice as fast as slow pointer [OK]

Common Mistakes:

• Swapping fast and slow pointer movements
• Not checking fast->next before fast->next->next
• Using slow pointer to move two steps

3. Given the linked list: 1 -> 2 -> 3 -> 4 -> 5 -> NULL, what is the reordered list after applying the reorder operation?

medium

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

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

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

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

Solution

1. Step 1: Identify the reorder pattern on the list

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

2. Step 2: Apply pattern to given list

   Start with 1, then 5, then 2, then 4, then 3. So reordered list is 1 -> 5 -> 2 -> 4 -> 3 -> NULL.

3. Final Answer:

   1 -> 5 -> 2 -> 4 -> 3 -> NULL -> Option D

4. Quick Check:

   Alternate front and back nodes [OK]

Hint: Alternate nodes from start and end [OK]

Common Mistakes:

• Reversing the entire list instead
• Keeping original order unchanged
• Skipping nodes or mixing order

4. Consider this buggy C code snippet for reordering a linked list. What is the main error?

void reorderList(Node* head) {
  Node *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next;
  }
  // further code omitted
}

medium

A. Fast pointer moves only one step instead of two

B. Slow pointer moves two steps instead of one

C. Missing check for head being NULL

D. Using wrong variable names for pointers

Solution

1. Step 1: Analyze pointer movements in the loop

   Fast pointer should move two steps to find middle, but here it moves only one step.

2. Step 2: Identify impact of incorrect fast pointer movement

   This causes slow pointer to not reach the true middle, breaking reorder logic.

3. Final Answer:

   Fast pointer moves only one step instead of two -> Option A

4. Quick Check:

   Fast must move 2 steps, not 1 [OK]

Hint: Fast pointer moves twice as fast as slow [OK]

Common Mistakes:

• Not moving fast pointer two steps
• Ignoring NULL checks
• Confusing slow and fast pointer roles

5. You have a linked list: 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> NULL. After reordering, what will be the list? Also, explain why the middle node is chosen as it is.

hard

A. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 40 because it's the node after center

B. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 30 because it's the exact center for even length

C. 10 -> 50 -> 20 -> 40 -> 30 -> 60 -> NULL; middle is 30 because it's the exact center

D. 10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 20 because it's the first half's end

Solution

1. Step 1: Find the middle node for even length list

   For 6 nodes, middle is node 3 (value 30) because slow pointer stops at exact center when fast moves two steps.

2. Step 2: Apply reorder pattern

   Reorder alternates nodes from start and end: 10, 60, 20, 50, 30, 40.

3. Final Answer:

   10 -> 60 -> 20 -> 50 -> 30 -> 40 -> NULL; middle is 30 because it's the exact center for even length -> Option B

4. Quick Check:

   Middle at center, reorder alternates front and back [OK]

Hint: Middle is center node; reorder alternates front and back [OK]

Common Mistakes:

• Choosing wrong middle for even length
• Mixing reorder order
• Confusing node positions