Start practising

Sort List

Medium Linked List Miscellaneous Original on LeetCode

Sort List is a medium linked list problem solved with the miscellaneous pattern. The best approach, optimal (top-down merge sort), runs in O(n log n) time and O(log n) space. Below are 2 approaches in Java, from copy, sort, write back up.

Problem

Sort a linked list in ascending order and return its head.

Examples

Example 1

Input
head = [4, 2, 1, 3]
Output
[1, 2, 3, 4]

Example 2

Input
head = [-1, 5, 3, 4, 0]
Output
[-1, 0, 3, 4, 5]

Constraints

  • The list has 0 to 5 * 10^4 nodes.
  • Follow-up: O(n log n) time and O(1) memory.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Copy, sort, write backO(n log n)O(n)
Optimal (top-down merge sort)O(n log n)O(log n)

1Copy, sort, write back

TimeO(n log n)
SpaceO(n)

Copy the values into an array, sort it and write the values back into the nodes.

  1. Collect values, Collections.sort, overwrite node values.
Java
class Solution {
    public ListNode sortList(ListNode head) {
        List<Integer> v = new ArrayList<>();
        for (ListNode p = head; p != null; p = p.next) v.add(p.val);
        Collections.sort(v);
        ListNode p = head;
        for (int x : v) { p.val = x; p = p.next; }
        return head;
    }
}

2Optimal (top-down merge sort)

TimeO(n log n)
SpaceO(log n)Recursion stack. A bottom-up merge sort gets this down to O(1).

Split the list at its middle (stop slow one node before the middle so you can cut), sort both halves recursively and merge them with a dummy node.

  1. If the list has 0 or 1 nodes, return it.
  2. slow = head, fast = head.next; advance to find the end of the first half; cut.
  3. Return merge(sort(left), sort(right)).
Java
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode right = slow.next;
        slow.next = null;
        return merge(sortList(head), sortList(right));
    }

    private ListNode merge(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(), t = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { t.next = a; a = a.next; }
            else { t.next = b; b = b.next; }
            t = t.next;
        }
        t.next = a != null ? a : b;
        return dummy.next;
    }
}

Edge cases to test

  • Empty list or one node
  • Already sorted input

Hints

Hint 1

Merge sort fits linked lists: splitting uses slow/fast pointers and merging needs no extra array.

FAQ

What is the best time complexity for Sort List?

Optimal (top-down merge sort) runs in O(n log n) time and O(log n) extra space.

Which pattern does Sort List use?

It is a linked list problem that uses the miscellaneous pattern. Other problems with the same pattern: Delete Node in a Linked List, Copy List with Random Pointer, Intersection of Two Linked Lists.

Is there a brute force solution for Sort List?

Yes. Copy, sort, write back takes O(n log n) time and O(n) space. Copy the values into an array, sort it and write the values back into the nodes.

Which edge cases should I test for Sort List?

Empty list or one node; Already sorted input.