AlgoViz
HomeLinked List

Sort LL

Hard

Merge sort, using the middle split

Problem

Given the head of a singly linked list. Sort the values of the linked list in non-decreasing order and return the head of the modified linked list.

In simple words

Split the list in halves with fast/slow pointers, sort each, and merge — merge sort on a list.

The idea

Split the list at its middle with slow and fast pointers, sort each half recursively, and merge the two sorted lists by repeatedly taking the smaller head. Merge sort suits lists because merging needs only pointer rewrites, not shifting.

The trick

  • Cut the list at the middle by nulling the predecessor's next.
  • O(n log n) time; the O(log n) recursion stack is the only extra space.
  • Quick sort is a poor fit here — lists have no random access for partitioning.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

5
6
1
2
1
0
1
2
3
4

Step 1 of 2. Here's the example — head -> 5 -> 6 -> 1 -> 2 -> 1 Values: 5, 6, 1, 2, 1.

1/2
Optimal
timeO(n log n)spaceO(log n)
1function sort(head):2  if head == null or head.next == null: return head3  mid = splitMiddle(head)          // slow/fast4  return merge(sort(head), sort(mid))

Input

array
[5, 6, 1, 2, 1]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 4 -> 2 -> 1 -> 3
Output:
1 -> 2 -> 3 -> 4
Explanation:
Merge-sort the list into order.

Example 2

Input:
list = -1 -> 5 -> 3 -> 4 -> 0
Output:
-1 -> 0 -> 3 -> 4 -> 5
Explanation:
Works with negatives too.

Example 3

Input:
list = 1
Output:
1
Explanation:
Already sorted.

Constraints

  • 0 <= number of nodes in the linked list <= 1000
  • -10^4 <= ListNode.val <= 10^4

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.