Sort the Nodes of a Linked List
Solve this Problemhead of a singly linked list, sort it in non-decreasing order and return the sorted list's head.
Because a linked list can't be randomly indexed the way an array can, most in-place sorting algorithms don't translate directly. Merge sortMerge Sort on a Linked ListA divide-and-conquer sort: split the list into two halves (using slow/fast pointers to find an even split point), recursively sort each half, then merge the two sorted halves back together. Unlike merge sort on an array, no auxiliary array is ever needed — splitting only cuts a link, and merging only re-links existing nodes. is the exception — it only ever needs sequential access, both to split the list (find a midpoint, cut the link) and to merge two already-sorted halves (walk both with two pointers, re-linking as you go, exactly like merging two sorted lists). That makes it a natural fit for a linked list, running in O(n log n) time using only O(log n) extra space for the recursion.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes in head ≤ 500 - ◆
-10⁵ ≤ node value ≤ 10⁵ - ◆
The list is not guaranteed to be sorted
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | private Node merge(Node a, Node b) { |
| 3 | Node dummy = new Node(0); |
| 4 | Node tail = dummy; |
| 5 | while (a != null && b != null) { |
| 6 | if (a.val <= b.val) { |
| 7 | tail.next = a; |
| 8 | a = a.next; |
| 9 | } else { |
| 10 | tail.next = b; |
| 11 | b = b.next; |
| 12 | } |
| 13 | tail = tail.next; |
| 14 | } |
| 15 | tail.next = (a != null) ? a : b; |
| 16 | return dummy.next; |
| 17 | } |
| 18 | |
| 19 | public Node sortLinkedList(Node head) { |
| 20 | if (head == null || head.next == null) { |
| 21 | return head; |
| 22 | } |
| 23 | Node slow = head; |
| 24 | Node fast = head.next; |
| 25 | while (fast != null && fast.next != null) { |
| 26 | slow = slow.next; |
| 27 | fast = fast.next.next; |
| 28 | } |
| 29 | Node right = slow.next; |
| 30 | slow.next = null; |
| 31 | Node left = sortLinkedList(head); |
| 32 | right = sortLinkedList(right); |
| 33 | return merge(left, right); |
| 34 | } |
| 35 | } |
| 36 |
42head (4) and head.next (2) are both non-null — this list has more than one node, so it isn't a base case yet.
Approach & Solutions
Brute Force — Collect Values, Sort, Overwrite
GoodWalk the list once, copying every node's value into an array. Sort that array with a general-purpose sort. Then walk the list a second time, overwriting each node's value in order from the sorted array — the nodes themselves never move, only what they hold changes. Correct, but it treats the linked list as nothing more than a container for values, throwing away any structure a solution could exploit, and needs O(n) extra space for the array.
O(n log n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node sortLinkedList(Node head) {
9 List<Integer> vals = new ArrayList<>();
10 Node curr = head;
11 while (curr != null) {
12 vals.add(curr.val);
13 curr = curr.next;
14 }
15 Collections.sort(vals);
16 curr = head;
17 for (int v : vals) {
18 curr.val = v;
19 curr = curr.next;
20 }
21 return head;
22 }
23}Optimal — Merge Sort on the Linked List
OptimalApply merge sort directly to the list structure, with no auxiliary array. Find the middle with slow/fast pointers — but offset fast to start one node ahead of slow, so the list splits into two genuinely even halves rather than landing on a single "middle" node. Cut the link there, recursively sort each half the same way (down to the base case of 0 or 1 nodes, which is already sorted), then merge the two sorted halves with the same splice-based two-pointer merge used to merge two sorted lists. The recursion depth is O(log n), which is the only extra space this solution needs.
O(n log n)O(log n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 private Node merge(Node a, Node b) {
9 Node dummy = new Node(0);
10 Node tail = dummy;
11 while (a != null && b != null) {
12 if (a.val <= b.val) {
13 tail.next = a;
14 a = a.next;
15 } else {
16 tail.next = b;
17 b = b.next;
18 }
19 tail = tail.next;
20 }
21 tail.next = (a != null) ? a : b;
22 return dummy.next;
23 }
24
25 public Node sortLinkedList(Node head) {
26 if (head == null || head.next == null) {
27 return head;
28 }
29 Node slow = head;
30 Node fast = head.next;
31 while (fast != null && fast.next != null) {
32 slow = slow.next;
33 fast = fast.next.next;
34 }
35 Node right = slow.next;
36 slow.next = null;
37 Node left = sortLinkedList(head);
38 right = sortLinkedList(right);
39 return merge(left, right);
40 }
41}