148. Sort List - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given the head of a singly linked list, sort the list in ascending order and return the sorted list. You must do this in O(n log n) time and O(1) (only for bottom‑up) or O(log n) (recursive splits) extra space.

Examples

Input: 4 → 2 → 1 → 3
Output: 1 → 2 → 3 → 4
Explanation: sort and relink nodes.

Input: -1 → 5 → 3 → 4 → 0
Output: -1 → 0 → 3 → 4 → 5

Input: (empty list)
Output: (empty list)

Constraints

The number of nodes in the list is in the range [0, 5·10⁴].
-10⁵ ≤ Node.val ≤ 10⁵

Hints

Can you sort by extracting values into an array, sorting them, then rebuilding the list?
How would you split the list into two halves, sort each half recursively, then merge?

Approach 1 – Brute Force

Explanation

Take advantage of built‑in array sort:

Traverse the list, copy all node values into a Python list / Java ArrayList.
Sort that list of values.
Create a new linked list by iterating sorted values and chaining new nodes.

This is easy but uses extra O(n) space.

Step‑by‑step Walkthrough

For 4 → 2 → 1 → 3:

Extract → [4,2,1,3]
Sort → [1,2,3,4]
Build new list → 1 → 2 → 3 → 4

Python Implementation

Python3

. . . .

Java Code

Java

. . . .

Approach 2 – Merge Sort (Optimal)

Explanation

Merge sort naturally fits linked lists:

Split the list into two halves via fast/slow pointers.
Recursively sort each half.
Merge the two sorted halves in linear time.

This achieves O(n log n) time and only O(log n) recursion space.

Step‑by‑step Walkthrough

For 4 → 2 → 1 → 3:

Find mid: slow at 2, fast at end → split into (4→2) and (1→3)
Recurse on 4→2 → splits to (4) & (2), merges to 2→4
Recurse on 1→3 → splits to (1) & (3), merges to 1→3
Merge 2→4 and 1→3: compare heads → 1,2,3,4

Visual Example

[4→2→1→3]
    ↓ split
[4→2]    [1→3]
  ↓ split    ↓ split
[4] [2]    [1] [3]
  ↓ merge   ↓ merge
[2→4]      [1→3]
    ↓ merge final
[1→2→3→4]

Python Implementation

Python3

. . . .

Java Implementation

Java

. . . .

Complexity Analysis

Approach 1 (array sort):
- Time O(n log n) for sorting
- Space O(n) for the array + new nodes
Approach 2 (merge sort):
- Time O(n log n) for split & merge
- Space O(log n) recursion stack (or O(1) if bottom‑up variant)