Sorting a Linked List

Medium

You are given head, the first node of a singly linked list (None if the list is empty). Arrange the nodes in non-decreasing order of their values and return the first node of the resulting list. Try to stay within O(n log n) time without copying the values into an array.

Example 1

head=list_node([7, -2, 7, 0]) → [-2, 0, 7, 7]

The values in non-decreasing order are -2, 0, 7, 7.

Example 2

head=list_node([3]) → [3]

A one-node list is already sorted.

Example 3

head=list_node([]) → None

Constraints

The list has between 0 and 5·10⁴ nodes
-10⁵ ≤ Node.val ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Linked List Two Pointers Divide and Conquer Sorting Merge Sort

Similar problems

Hand-Rolled Sort Medium From Absolute Order to Actual Order Medium Merge Many Sorted Chains Hard Zero-Sum Triples Medium Triple Sum Nearest the Target Medium

Input

head=list_node([7, -2, 7, 0])

Expected

[-2, 0, 7, 7]

Run checks the first 3 tests in your browser. Submit checks all 110 tests on the server, hidden ones included.