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.