Reorder Linked List in DSA C - Time & Space Complexity

Time Complexity: Reorder Linked List

O(n)

Understanding Time Complexity

We want to understand how the time needed to reorder a linked list changes as the list grows.

Specifically, how the steps increase when we rearrange nodes in a special order.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Reorder linked list: L0->L1->...->Ln-1->Ln to L0->Ln->L1->Ln-1->...
void reorderList(ListNode* head) {
    if (!head || !head->next) return;

    // Find middle
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Reverse second half
    ListNode* prev = NULL;
    ListNode* curr = slow;
    while (curr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }

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

This code reorders a linked list by first finding the middle, reversing the second half, then merging the two halves in alternating order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the list multiple times: once to find middle, once to reverse, once to merge.
• How many times: Each traversal goes through about n/2 to n nodes, where n is list length.

How Execution Grows With Input

As the list size grows, each step takes longer roughly proportional to the number of nodes.

Input Size (n)	Approx. Operations
10	About 30 steps (3 passes of ~10 nodes)
100	About 300 steps
1000	About 3000 steps

Pattern observation: The total steps grow roughly in a straight line with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to reorder grows directly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Reversing the second half or merging halves takes more than linear time because it looks complicated."

[OK] Correct: Each step only visits each node once or twice, so total work is still proportional to n, not more.

Interview Connect

Understanding this helps you explain how to handle linked lists efficiently, a common skill interviewers look for.

Self-Check

"What if we used recursion to reverse the second half instead of a loop? How would the time complexity change?"