Sort List

You are given the head of a singly linked list of integers. Rearrange the list so that its values appear in non-decreasing order and return the new head.

Aim for O(n log n) time. You may relink the existing nodes rather than creating new ones. An empty list is valid input and should come back empty.

Lists are written as arrays in the tests, head first.

Example 1

Example 2

Example 3

Constraints

• 0 <= number of nodes <= 5 · 104
• -105 <= Node.val <= 105

Pattern Path · Linked Lists · problem 75 of 169

Start simple

Insertion sort on the list, or copy values into an array, sort it and write them back: O(n²) for insertion sort, or O(n) extra memory for the copy.

The key idea

Quicksort and heapsort rely on jumping to arbitrary positions, which a linked list cannot do cheaply. Merge sort only ever walks sequences front to back, so it fits linked lists perfectly.

1. Split. Use a slow pointer and a fast pointer (two steps at a time) to find the middle, then set slow.next = null to cut the list into two halves.
2. Recurse. Sort each half. A list of zero or one node is already sorted.
3. Merge. Repeatedly take the smaller head of the two sorted halves and append it to a tail pointer that starts at a dummy node. When one half runs out, attach the rest of the other.

Each level of recursion touches every node once, and halving gives about log n levels, so the time is O(n log n). Merging only relinks next pointers, so no node is copied; the only extra memory is the O(log n) recursion stack. Taking from the left half on ties also makes the sort stable.

Complexity

• Time: O(n log n)
• Space: O(log n) recursion stack

Python

class Solution:
    def sortList(self, head):
        if head is None or head.next is None:
            return head
        # Find the middle: slow ends on the last node of the left half.
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        right = slow.next
        slow.next = None  # cut the list in two
        return self.merge(self.sortList(head), self.sortList(right))

    def merge(self, a, b):
        dummy = tail = ListNode(0)
        while a and b:
            if a.val <= b.val:
                tail.next, a = a, a.next
            else:
                tail.next, b = b, b.next
            tail = tail.next
        tail.next = a or b  # attach whatever remains
        return dummy.next

JavaScript

var sortList = function(head) {
  if (head === null || head.next === null) return head;
  // Find the middle: slow ends on the last node of the left half.
  let slow = head, fast = head.next;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  const right = slow.next;
  slow.next = null; // cut the list in two
  return merge(sortList(head), sortList(right));
};

function merge(a, b) {
  const dummy = new ListNode(0);
  let tail = dummy;
  while (a && b) {
    if (a.val <= b.val) { tail.next = a; a = a.next; }
    else { tail.next = b; b = b.next; }
    tail = tail.next;
  }
  tail.next = a || b; // attach whatever remains
  return dummy.next;
}

What the interviewer is checking

It combines three linked-list building blocks (find the middle, cut, merge two sorted lists) and checks that you can pick an algorithm that suits sequential access.

Mistakes to avoid

• Starting fast at head instead of head.next: with two nodes the split never shrinks and the recursion never ends.
• Forgetting to cut the list (slow.next = null), so the left half still includes the right half.
• Not handling the empty list or a single node as base cases.
• Copying values to an array, which ignores the spirit of the problem and uses O(n) memory.

Follow-ups to expect

• Can you do it with O(1) extra space? (Bottom-up iterative merge sort.)
• How would you merge k sorted lists? (Min-heap or pairwise merging.)
• Is your sort stable? (Yes, if ties take from the left.)

In real software

External sorting of data too big for memory streams sorted runs from disk and merges them sequentially, which is the same merge-sort-on-sequences idea used here.

Practice next