
解题思路:
- 找到链表中点: 使用快慢指针法,快指针每次移动两步,慢指针每次移动一步。当快指针到达末尾时,慢指针指向中点。
- 递归分割与排序: 将链表从中点处分割为左右两个子链表,分别对这两个子链表递归排序。
- 合并有序子链表: 将两个已排序的子链表合并成一个有序链表。
Java代码:
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
}
复杂度分析:
- 时间复杂度: 归并排序的时间复杂度为 O(nlogn)。
- 空间复杂度: O(log n)。(递归栈深度)

解题思路:
- 初始化优先队列: 将所有链表的头节点加入堆中,堆顶元素为当前最小值。
- 构建结果链表: 每次从堆顶取出最小节点,添加到结果链表中,并将其下一个节点加入堆中(若存在)。
- 处理空链表: 跳过输入数组中的空链表,避免无效操作。
Java代码:
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);
for (ListNode node : lists) {
if (node != null) {
minHeap.offer(node);
}
}
ListNode dummy = new ListNode(-1);
ListNode current = dummy;
while (!minHeap.isEmpty()) {
ListNode smallest = minHeap.poll();
current.next = smallest;
current = current.next;
if (smallest.next != null) {
minHeap.offer(smallest.next);
}
}
return dummy.next;
}
}
复杂度分析:
- 时间复杂度: O(nklogk),其中 n 是总节点数,k 是链表数量。
- 空间复杂度: O(k),用于存储堆中的节点。