#148
Sort List
Medium Merge sort on a linked list
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Sort a singly linked list in O(n log n) time.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: sort a linked list in O(n log n).
Why this works: merge sort only needs to walk forward: find the middle, cut, sort both halves, merge.
Example: 4 → 2 → 1 → 3
halves 4→2 and 1→3 → sorted 2→4 and 1→3merge → 1→2→3→4
✦Hints open one at a time
Merge sort fits linked lists well: no random access needed.
Find the middle with slow/fast pointers and cut the list in two.
Merge the two sorted halves like "Merge Two Sorted Lists".
↗Approach
Split at the middle (stop fast one step early so the left half is not empty-looped), sort both halves recursively, and merge with a dummy head.
</>Solution (Java)
/**
* Definition for singly-linked list (provided by LeetCode):
* class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode right = slow.next;
slow.next = null; // cut into two halves
return merge(sortList(head), sortList(right));
}
private ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), tail = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { tail.next = a; a = a.next; }
else { tail.next = b; b = b.next; }
tail = tail.next;
}
tail.next = (a != null) ? a : b;
return dummy.next;
}
}!Common mistake
Not cutting the list (setting mid.next = null), which makes the recursion never shrink.
Complexity
- Time: O(n log n).
- Space: O(log n) recursion stack.
Topic: Sorting
🎬 Episodes 24–28: video coming soon