☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Sort LL

Hard TUF ID 616 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list. Return the head of the list sorted in non-decreasing order. The follow-up asks for O(n log n) time and O(1) extra memory (not counting the recursion stack, or ideally without recursion at all).

Constraints: 0 ≤ n ≤ 5 × 10^4 nodes, values fit in a 32-bit signed integer.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

head = 4 -> 2 -> 1 -> 3
answer = 1 -> 2 -> 3 -> 4

Example 2

head = -1 -> 5 -> 3 -> 4 -> 0
answer = -1 -> 0 -> 3 -> 4 -> 5      // negatives sort first

Example 3

head = (empty)
answer = (empty)

Approach 1: Brute force, sort an array of the values

Intuition. Sorting arrays is a solved problem. Copy the values into an array, call Arrays.sort, then walk the list again and write the sorted values back into the nodes. The chain of nodes never changes; only the values inside them do.

Algorithm.

  1. Count the nodes and allocate an int[] of that size.
  2. Copy every value into the array.
  3. Sort the array.
  4. Walk the list again and overwrite each node’s value with the next array element.
static ListNode bruteForce(ListNode head) {
    int n = 0;
    for (ListNode t = head; t != null; t = t.next) n++;
    int[] values = new int[n];
    int i = 0;
    for (ListNode t = head; t != null; t = t.next) values[i++] = t.val;
    Arrays.sort(values);
    i = 0;
    for (ListNode t = head; t != null; t = t.next) t.val = values[i++];
    return head;
}

Complexity. Time O(n log n) for the sort; the copies are O(n). Space O(n) for the array.

This meets the time bound but not the memory bound, and it moves values rather than nodes. Many problems care about the latter: the caller may hold a reference to a node and expect it to keep its value.

Approach 2: Optimal, top-down merge sort on the list

Intuition. Merge sort is the natural algorithm for linked lists. Quick sort and heap sort depend on random access, which a list does not have, but merge sort only needs two things that lists do well: splitting a list in half (find the middle with slow and fast pointers and cut the link) and merging two sorted lists (compare heads, re-link the smaller one). No values are copied; nodes are simply re-threaded.

Algorithm.

  1. If the list has 0 or 1 nodes, it is sorted; return it.
  2. Find the last node of the first half with slow and fast pointers, remember rightHead = mid.next, and set mid.next = null to cut the list in two.
  3. Recursively sort both halves.
  4. Merge the two sorted halves and return the merged head.
static ListNode optimal(ListNode head) {
    if (head == null || head.next == null) return head;   // 0 or 1 node is already sorted
    ListNode mid = lastOfFirstHalf(head);
    ListNode rightHead = mid.next;
    mid.next = null;                                       // cut the list into two independent halves
    ListNode left = optimal(head);
    ListNode right = optimal(rightHead);
    return merge(left, right);
}

Finding the cut point: fast starts one node ahead so that, for an even number of nodes, slow stops at the end of the first half rather than the start of the second. For two nodes, slow stays on the first node and the halves are one node each, which is what guarantees the recursion shrinks.

static ListNode lastOfFirstHalf(ListNode head) {
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

Merging two sorted lists with a dummy head avoids special-casing the first node. The <= makes ties take from the left run first, which keeps equal values in their original order (a stable sort).

static ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;                       // whatever is left is already sorted
    return dummy.next;
}

Dry run on 4 -> 2 -> 1 -> 3:

call input split result
sort 4 2 1 3 4 2 and 1 3 merge(2 4, 1 3) = 1 2 3 4
sort 4 2 4 and 2 merge(4, 2) = 2 4
sort 1 3 1 and 3 merge(1, 3) = 1 3

Complexity. Time O(n log n): there are log n levels of recursion and each level splits and merges a total of n nodes. Space O(log n) for the recursion stack; no array is allocated.

Approach 3: Optimal without recursion, bottom-up merge sort

Intuition. The recursion in the top-down version only decides which pieces get merged when. We can schedule the merges explicitly instead: first merge runs of size 1 into sorted runs of size 2, then runs of size 2 into runs of size 4, and so on, until a single run of size n remains. Each pass walks the list once, cutting off two runs of the current size, merging them, and attaching the result after the previously merged part. This removes the recursion stack and makes the extra memory truly O(1).

Algorithm.

  1. Count the nodes and create a dummy node in front of head.
  2. For size = 1, 2, 4, ... while size < n:
    • Set prev = dummy, cur = dummy.next.
    • While cur is non-null: cut left (at most size nodes) from cur, cut right (at most size nodes) from what follows, and remember the rest in cur. Merge left and right, attach the merged run after prev, and move prev to the end of the merged run.
  3. Return dummy.next.
static ListNode optimalBottomUp(ListNode head) {
    int n = 0;
    for (ListNode t = head; t != null; t = t.next) n++;
    ListNode dummy = new ListNode(0, head);
    for (int size = 1; size < n; size *= 2) {
        ListNode prev = dummy, cur = dummy.next;
        while (cur != null) {
            ListNode left = cur;
            ListNode right = split(left, size);            // left now holds at most size nodes
            cur = split(right, size);                      // right now holds at most size nodes; cur is the rest
            prev = mergeAfter(prev, left, right);          // attach the merged run after prev
        }
    }
    return dummy.next;
}

The two helpers: split cuts after at most size nodes and returns what remains, and mergeAfter merges two runs directly after a given node and returns the new tail so the next merge knows where to attach.

static ListNode split(ListNode head, int size) {
    if (head == null) return null;
    for (int i = 1; i < size && head.next != null; i++) head = head.next;
    ListNode rest = head.next;
    head.next = null;
    return rest;
}

static ListNode mergeAfter(ListNode prev, ListNode a, ListNode b) {
    ListNode tail = prev;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    while (tail.next != null) tail = tail.next;            // walk to the end of the merged run
    return tail;
}

Complexity. Time O(n log n): log n passes, each visiting every node a constant number of times. Space O(1): a dummy node and a few pointers, no recursion.

The Java file tests all three methods against Arrays.sort on the same inputs, including a 100 000-node pseudo-random list (seeded Random) and a list of 65 537 nodes, whose size is not a power of two so the bottom-up passes must handle uneven final runs. For the two re-linking methods it also verifies that the output consists of exactly the original node objects.

Edge cases and pitfalls