LeetCode 148: Sort List (Linked List Merge Sort, O(n log n))
LeetCode 148Linked ListMerge SortToday we solve LeetCode 148 - Sort List.
Source: https://leetcode.com/problems/sort-list/
English
Problem Summary
Given the head of a singly linked list, sort the list in ascending order and return the sorted head.
Key Insight
Array sort is easy but linked lists do not support random access. Merge sort fits linked lists naturally: split by fast/slow pointers, recursively sort halves, then merge two sorted lists in linear time.
Brute Force and Limitations
Copy all values into an array, sort, then rebuild list. This works but uses extra O(n) memory and misses the linked-list technique expected by this problem.
Optimal Algorithm Steps
1) Base case: empty list or one node is already sorted.
2) Use slow/fast pointers to find middle; cut list into two halves.
3) Recursively sort left and right halves.
4) Merge two sorted linked lists with a dummy head.
5) Return merged head.
Complexity Analysis
Time: O(n log n) (each level merges n nodes, about log n levels).
Space: O(log n) recursion stack (node storage reused).
Common Pitfalls
- Forgetting to cut at middle (prev.next = null) causing infinite recursion.
- Wrong middle split on even-length lists.
- Breaking merged chain by advancing pointers incorrectly.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
ListNode left = sortList(head);
ListNode right = sortList(slow);
return merge(left, right);
}
private ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), cur = dummy;
while (a != null && b != null) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
cur.next = (a != null) ? a : b;
return dummy.next;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
var prev *ListNode
slow, fast := head, head
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
prev.Next = nil
left := sortList(head)
right := sortList(slow)
return merge(left, right)
}
func merge(a, b *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for a != nil && b != nil {
if a.Val <= b.Val {
cur.Next = a
a = a.Next
} else {
cur.Next = b
b = b.Next
}
cur = cur.Next
}
if a != nil {
cur.Next = a
} else {
cur.Next = b
}
return dummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *slow = head, *fast = head, *prev = nullptr;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr;
ListNode* left = sortList(head);
ListNode* right = sortList(slow);
return merge(left, right);
}
private:
ListNode* merge(ListNode* a, ListNode* b) {
ListNode dummy(0);
ListNode* cur = &dummy;
while (a && b) {
if (a->val <= b->val) {
cur->next = a;
a = a->next;
} else {
cur->next = b;
b = b->next;
}
cur = cur->next;
}
cur->next = a ? a : b;
return dummy.next;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head):
if not head or not head.next:
return head
prev = None
slow, fast = head, head
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
left = self.sortList(head)
right = self.sortList(slow)
return self.merge(left, right)
def merge(self, a, b):
dummy = ListNode(0)
cur = dummy
while a and b:
if a.val <= b.val:
cur.next = a
a = a.next
else:
cur.next = b
b = b.next
cur = cur.next
cur.next = a if a else b
return dummy.next/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var sortList = function(head) {
if (!head || !head.next) return head;
let prev = null, slow = head, fast = head;
while (fast && fast.next) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
const left = sortList(head);
const right = sortList(slow);
return merge(left, right);
};
function merge(a, b) {
const dummy = new ListNode(0);
let cur = dummy;
while (a && b) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
cur.next = a || b;
return dummy.next;
}中文
题目概述
给你一个单链表头结点 head，请将链表按升序排序并返回排序后的链表。
核心思路
链表不适合随机访问，快速排序分区实现也更麻烦。归并排序非常契合链表：快慢指针拆分 + 线性归并，整体稳定且容易保证正确性。
暴力解法与不足
把链表值拷贝到数组、排序后再重建链表能做出来，但额外占用 O(n) 空间，也偏离了链表本身的经典解法。
最优算法步骤
1）空链表或单节点直接返回。
2）快慢指针找中点，并把链表断成两半。
3）递归排序左右两段。
4）用虚拟头结点把两个有序链表归并。
5）返回归并后的头结点。
复杂度分析
时间复杂度：O(n log n)。
空间复杂度：O(log n)（递归栈）。
常见陷阱
- 忘记断链导致递归无法收敛。
- 中点处理错误导致左右不平衡或丢节点。
- 归并时指针推进顺序写错。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head, prev = null;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
ListNode left = sortList(head);
ListNode right = sortList(slow);
return merge(left, right);
}
private ListNode merge(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), cur = dummy;
while (a != null && b != null) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
cur.next = (a != null) ? a : b;
return dummy.next;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
var prev *ListNode
slow, fast := head, head
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
prev.Next = nil
left := sortList(head)
right := sortList(slow)
return merge(left, right)
}
func merge(a, b *ListNode) *ListNode {
dummy := &ListNode{}
cur := dummy
for a != nil && b != nil {
if a.Val <= b.Val {
cur.Next = a
a = a.Next
} else {
cur.Next = b
b = b.Next
}
cur = cur.Next
}
if a != nil {
cur.Next = a
} else {
cur.Next = b
}
return dummy.Next
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode *slow = head, *fast = head, *prev = nullptr;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr;
ListNode* left = sortList(head);
ListNode* right = sortList(slow);
return merge(left, right);
}
private:
ListNode* merge(ListNode* a, ListNode* b) {
ListNode dummy(0);
ListNode* cur = &dummy;
while (a && b) {
if (a->val <= b->val) {
cur->next = a;
a = a->next;
} else {
cur->next = b;
b = b->next;
}
cur = cur->next;
}
cur->next = a ? a : b;
return dummy.next;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def sortList(self, head):
if not head or not head.next:
return head
prev = None
slow, fast = head, head
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
left = self.sortList(head)
right = self.sortList(slow)
return self.merge(left, right)
def merge(self, a, b):
dummy = ListNode(0)
cur = dummy
while a and b:
if a.val <= b.val:
cur.next = a
a = a.next
else:
cur.next = b
b = b.next
cur = cur.next
cur.next = a if a else b
return dummy.next/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var sortList = function(head) {
if (!head || !head.next) return head;
let prev = null, slow = head, fast = head;
while (fast && fast.next) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
const left = sortList(head);
const right = sortList(slow);
return merge(left, right);
};
function merge(a, b) {
const dummy = new ListNode(0);
let cur = dummy;
while (a && b) {
if (a.val <= b.val) {
cur.next = a;
a = a.next;
} else {
cur.next = b;
b = b.next;
}
cur = cur.next;
}
cur.next = a || b;
return dummy.next;
}
Comments