Problem statement

Given the head of a singly linked list, return the list sorted in ascending order.

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]

Example 3

Input: head = []
Output: []

Constraints

• The number of nodes in the list is in the range [0, 5 * 10^4]
• -10^5 <= Node.val <= 10^5

Follow-up: Can you sort the list in O(n log n) time with only O(1) extra memory (the bottom-up merge sort)?

Hints for Sort List

1. Hint 1

   Quadratic sorts are too slow for 5·10^4 nodes; merge sort suits linked lists because merging needs no random access.

2. Hint 2

   Split the list in half with slow and fast pointers, sort each half recursively, and merge the two sorted halves.

3. Hint 3

   Merging two sorted lists takes a dummy node and a tail pointer. Cut the first half off (slow.next = null) before recursing.

How to solve Sort List

Top-down merge sort on the links: find the middle, cut the list in two, sort each half recursively, then merge. Lists are a natural fit — splitting and merging only move pointers.

Approach

1. If the list has 0 or 1 nodes, it is sorted; return it.
2. Find the middle: slow = head, fast = head.next; while fast and fast.next exist, advance slow once and fast twice.
3. right = slow.next; cut with slow.next = null.
4. Recursively sort head and right, then merge them: repeatedly append the smaller head to a tail pointer behind a dummy node, then attach whatever remains.
5. Return the merged head.

Why it works

Starting fast at head.next makes slow stop at the end of the first half, so both halves are non-empty and strictly shorter, and the recursion terminates. Merging two sorted lists by always taking the smaller head yields a sorted list of all their nodes, so by induction every call returns its nodes sorted.

Complexity

• Time — O(n log n)
• Space — O(log n) for the recursion; the bottom-up variant that merges runs of size 1, 2, 4, … uses O(1)

Pitfalls

• Starting fast at head leaves a two-node list split into 2 + 0 and recursing forever.
• Forgetting to cut the first half off makes the recursion see the whole list again.
• Insertion sort or repeated minimum selection is O(n²) and times out on the full constraints.

Reference solution

Python

from typing import Optional

def sortList(head: Optional[ListNode]) -> Optional[ListNode]:
    if head is None or head.next is None:
        return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    right = slow.next
    slow.next = None
    a, b = sortList(head), sortList(right)
    dummy = ListNode(0)
    tail = dummy
    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 if a else b
    return dummy.next

Java

public static 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;
    ListNode a = sortList(head), b = sortList(right);
    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;
    return dummy.next;
}

C++

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* right = slow->next;
    slow->next = nullptr;
    ListNode* a = sortList(head);
    ListNode* b = sortList(right);
    ListNode dummy(0);
    ListNode* 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 ? a : b;
    return dummy.next;
}

JavaScript

var sortList = function(head) {
    if (head === null || head.next === null) return head;
    var slow = head, fast = head.next;
    while (fast !== null && fast.next !== null) { slow = slow.next; fast = fast.next.next; }
    var right = slow.next;
    slow.next = null;
    var a = sortList(head), b = sortList(right);
    var 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;
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More sorting problems

• Tweet Counts Per Frequency Medium
• Merge Two Sorted Linked Lists in Reverse Order Medium
• Union of Two Linked Lists Medium
• Insertion Sort List Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium
• Kth Largest Sum in a Binary Tree Medium