面试遇到的一道题，链表排序。
文章目录
- 链表排序
- 1. 题目描述
- 2. 思路分析
- 3. 代码实现
链表排序
1. 题目描述
leetcode题目链接：148. 排序链表
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
2. 思路分析
这道题考虑时间复杂度优于 O(n2) 的排序算法。题目的进阶问题要求达到 O(nlogn)的时间复杂度和 O(1) 的空间复杂度，时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是 O(n2)，其中最适合链表的排序算法是归并排序。
方法一：堆排序
最简单直接的方法：
- 定义类型为ListNode的最小堆
- 建堆：链表所有node入堆
- 依次弹出堆顶node，即是从小到大的顺序
- 时间复杂度O(nlogn)，空间复杂度O(n)
- 此法和数组的堆排序几乎没有区别，实现起来最简单，不易出错
方法二：自顶向下归并排序
优化空间复杂度。
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并，得到完整的排序后的链表。可以参考：21. 合并两个有序链表
上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序。
复杂度分析
方法三：自底向上归并排序
进一步优化空间复杂度。
空间复杂度 O(1)。从单个节点开始两两合并成多段有序链表；将多段有序链表再两两合并，直到合并成一个完整链表。
3. 代码实现
方法一：堆排序
class Solution {
public ListNode sortList(ListNode head) {
// 堆排序
PriorityQueue<ListNode> queue = new PriorityQueue<>((a, b) -> a.val - b.val); // 小顶堆
while (head != null) { // 全部加入小顶堆
queue.offer(head);
head = head.next;
}
// 出堆，赋值给新的链表
ListNode dumpy = new ListNode();
ListNode cur = dumpy;
while (queue.size() > 0) {
cur.next = queue.poll();
cur = cur.next;
}
cur.next = null;
return dumpy.next;
}
}
方法二：自顶向下归并排序
class Solution {
public ListNode sortList(ListNode head) {
// 如果链表为空，或者只有一个节点，直接返回，不用排序
if (head == null || head.next == null) return head;
// 快慢双指针移动，寻找中间节点
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 找到中间节点，slow节点的next指针指向mid
ListNode mid = slow.next;
// 切断链表
slow.next = null;
// 排序左子链表
ListNode left = sortList(head);
// 排序右子链表
ListNode right = sortList(mid);
// 合并链表
return merge(left, right);
}
public ListNode merge(ListNode left, ListNode right) { // 合并两个有序链表
ListNode head = new ListNode(0);
ListNode tmp = head;
while (left != null && right != null) {
if (left.val <= right.val) {
tmp.next = left;
left = left.next;
} else {
tmp.next = right;
right = right.next;
}
tmp = tmp.next;
}
if (left != null) {
tmp.next = left;
} else if (right != null) {
tmp.next = right;
}
return head.next;
}
}
方法三：自底向上归并排序
class Solution {
public ListNode sortList(ListNode head) {
// 自底向上归并排序
// 如果链表为空，或者只有一个节点，直接返回，不用排序
if (head == null || head.next == null) return head;
// 1. 遍历一遍，统计链表长度
int length = 0;
ListNode node = head;
while (node != null) {
length++;
node = node.next;
}
// 2. 初始化
ListNode dummy = new ListNode(0);
dummy.next = head;
// 3. 每次将链表拆分成若干个长度为subLen的子链表 , 并按照每两个子链表一组进行合并
for (int subLen = 1; subLen < length; subLen <<= 1) { // subLen每次左移一位（即sublen = sublen*2）
ListNode pre = dummy;
ListNode cur = dummy.next; // 用于记录拆分链表的位置
while (cur != null) {
// 3.1 拆分subLen长度的链表1
ListNode first = cur; // 第一个链表的头 即 cur初始的位置
for (int i = 1; i < subLen && cur != null && cur.next != null; i++) { // 拆分出长度为subLen的链表1
cur = cur.next;
}
// 3.2 拆分subLen长度的链表2
ListNode second = cur.next; // 第二个链表的头 即 链表1尾部的下一个位置
cur.next = null; // 断开第一个链表和第二个链表的链接
cur = second; // 第二个链表头 重新赋值给cur
for(int i = 1; i < subLen && cur != null && cur.next != null; i++){ // 再拆分出长度为subLen的链表2
cur = cur.next;
}
// 3.3 再次断开 第二个链表最后的next的链接
ListNode next = null;
if (cur != null) {
next = cur.next; // next用于记录 拆分完两个链表的结束位置
cur.next = null; // 断开连接
}
// 合并两个subLen长度的有序链表
ListNode merged = merge(first, second);
pre.next = merged; // pre.next 指向排好序链表的头
while (pre. next != null) { // while循环 将pre移动到 subLen*2 的位置后去
pre = pre.next;
}
cur = next; // next用于记录 拆分完两个链表的结束位置
}
}
// 返回新排序好的链表
return dummy.next;
}
public ListNode merge(ListNode left, ListNode right) { // 合并两个有序链表
ListNode head = new ListNode(0);
ListNode tmp = head;
while (left != null && right != null) {
if (left.val <= right.val) {
tmp.next = left;
left = left.next;
} else {
tmp.next = right;
right = right.next;
}
tmp = tmp.next;
}
if (left != null) {
tmp.next = left;
} else if (right != null) {
tmp.next = right;
}
return head.next;
}
}
