Back

Sort List

medium

Given the head of a linked list, return the list after sorting it in ascending order.

Can you sort the linked list in O(n log n) time and O(1) memory (i.e. constant space)?

Test Cases

Copy an input into the main harness and Run to verify
Input
head = [4,2,1,3]
Expected Output
[1,2,3,4]
Input
head = [-1,5,3,4,0]
Expected Output
[-1,0,3,4,5]
Input
head = []
Expected Output
[]

Constraints

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

Hints

Hint 1 — click to reveal

Quicksort needs random access; merge sort does not — it only ever walks forward.

Hint 2 — click to reveal

Split at the middle, sort each half recursively, then merge two sorted lists.

Java Compiler

Powered by OneCompiler. Starter code loads automatically — edit and hit Run.