Sort List

Intuitionwhy bottom-up merging fits a singly linked list

A linked list gives you sequential access but no useful way to jump to the middle or shift a block of values. That makes array-style sorting methods awkward. Merge sort matches the structure better: split the list into sorted pieces, then combine neighboring pieces by relinking existing nodes in ascending order.

The recursive version splits until every piece has one node, but its call stack uses O(log n) extra memory. You can remove that stack by starting with runs of length 1, merging adjacent runs, then repeating with lengths 2, 4, 8, and so on. After each round, every run is sorted, and doubling the run length guarantees that the whole list becomes sorted after O(log n) rounds.

Approachsplit runs, merge them, and reconnect the list

1. 1Return immediately for an empty list or a one-node list, because both are already sorted and have no pair of runs to merge.
2. 2Count the nodes once and use that length to control the run sizes, because a singly linked list cannot tell you its length or jump to a power-of-two boundary without walking it.
3. 3Place a dummy node before the head and start each pass with prev at the dummy, because the first merge can change the real head and still needs the same relinking logic as every later merge.
4. 4For each current position, take a left run of length step and then a right run of length step, cutting both runs at their boundaries, because merge must see two independent lists rather than accidentally walking into the following run.
5. 5Merge the two sorted runs by attaching the smaller front node after prev, then append the unconsumed remainder, because every node is already in one of the two sorted runs and only their front nodes can be the next global node.
6. 6Advance prev to the tail of the merged result and continue from the first node after the right run, because the next pair must be attached after the entire result and must not be merged again in the same pass.
7. 7Double step after the pass and return dummy.next when step reaches the list length, because each pass creates sorted runs twice as large and the dummy's next pointer is the final head even if the original head moved.

Complexitythe bound does not depend on how the nodes are arranged

Annotated solutionC++ · iterative bottom-up merge sort · constant extra space

#include <cstddef>

using namespace std;

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        int length = 0;
        for (ListNode* node = head; node != nullptr; node = node->next) {
            ++length;
        }

        ListNode dummy(0);
        dummy.next = head;

        for (int step = 1; step < length; step <<= 1) {
            ListNode* prev = &dummy;
            ListNode* current = dummy.next;

            while (current != nullptr) {
                ListNode* left = current;
                ListNode* right = split(left, step);
                current = split(right, step);
                prev = merge(left, right, prev);
            }
        }

        return dummy.next;
    }

private:
    ListNode* split(ListNode* head, int count) {
        for (int i = 1; head != nullptr && i < count; ++i) {
            head = head->next;
        }

        if (head == nullptr) {
            return nullptr;
        }

        ListNode* next = head->next;
        head->next = nullptr;
        return next;
    }

    ListNode* merge(ListNode* left, ListNode* right, ListNode* previous) {
        while (left != nullptr && right != nullptr) {
            if (left->val <= right->val) {
                previous->next = left;
                left = left->next;
            } else {
                previous->next = right;
                right = right->next;
            }
            previous = previous->next;
        }

        previous->next = (left != nullptr) ? left : right;

        while (previous->next != nullptr) {
            previous = previous->next;
        }
        return previous;
    }
};

The two helper functions carry the pointer-sensitive work. split cuts after at most step nodes and returns the first node after that run; if the list ends early, it simply returns null. merge receives detached runs, attaches nodes through previous, and walks to the new tail so the next pair can be appended without searching from the dummy again.

The recursive alternativesimpler to explain, but it gives up the constant-space requirement

Top-down recursive merge sort is a reasonable implementation when the constant-space requirement is absent. It is often shorter conceptually: find the midpoint with slow and fast pointers, recursively sort both halves, and merge them. It keeps the same O(n log n) time, but the recursion stack uses O(log n) extra space, so it is not a valid replacement for this problem's required bound.

#include <cstddef>

using namespace std;

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

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

        ListNode* right = slow->next;
        slow->next = nullptr;

        ListNode* leftSorted = sortList(head);
        ListNode* rightSorted = sortList(right);
        return merge(leftSorted, rightSorted);
    }

private:
    ListNode* merge(ListNode* left, ListNode* right) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        while (left != nullptr && right != nullptr) {
            if (left->val <= right->val) {
                tail->next = left;
                left = left->next;
            } else {
                tail->next = right;
                right = right->next;
            }
            tail = tail->next;
        }

        tail->next = (left != nullptr) ? left : right;
        return dummy.next;
    }
};

This alternative is a different arrangement of the same merge-sort idea, not an optimisation. It buys a direct expression of divide and conquer, but the runtime call stack grows with the number of splits. The bottom-up version moves that bookkeeping into a run-size loop and therefore satisfies the O(1) extra-space requirement.

Common mistakesthe pointer lines that change a correct sort into a broken traversal