题目
题目
思路
时间复杂度是O(nlogn)的排序算法包括归并排序、堆排序和快速排序（快速排序的最差时间复杂度是O()），其中最适合链表的排序算法是归并排序。
归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现，考虑到递归调用到栈空间，自顶向下归并排序的空间复杂度是O(logn)，如果要达到O(1)的空间复杂度，则需要使用自底向上的实现方式。
自顶向下归并排序
- 过程：
- 找到链表的中点（快慢指针），以中点为分界，将链表拆分成两个子链表。
- 对两个子链表分别排序
- 将两个排序后的子链表合并，得到完整的排序后的链表
- 递归的终止条件：
链表的节点个数小于或等于1 - 实现：
class Solution {
public ListNode sortList(ListNode head) {
return sortList(head);
}
public ListNode sort(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode head2 = slow.next;
slow.next = null;
return merge(sort(head), sort(head2));
}
public ListNode merge(ListNode head1, ListNode head2) {
ListNode dummtHead = new ListNode(0);
ListNode temp = dummyHead;
ListNode temp1 = head1;
ListNode temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
if (temp1 != null) {
temp.next = temp1;
} else if (temp2 != null) {
temp.next = temp2;
}
return dummyHead.next;
}
}
自底向上归并排序
- 过程
- 首先求得链表的长度length
- 用subLength表示每次需要排序的子链表的长度，初识时subLength=1
- 每次将链表拆分成若干个长度为subLength的子链表（最后一个子链表的长度可以小于subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为subLength x 2的有序子链表（最后一个子链表的长度可以小于subLength x 2）。
- 将subLength的值加倍(左移)，重复第三步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于length，整个链表排序完成
- 实现
class Solution {
public ListNode sortList(ListNode head) {
if (head == null) {
return head;
}
// 首先从头向后遍历，统计链表长度
int length = 0;
ListNode node = head;
while (node != null) {
length++;
node = node.next;
}
// 初始化
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
// 每次将链表拆分成若干个长度为subLength的子链表，并按照每两个子链表为一组进行合并
for (int subLength = 1; subLength < length; subLength << 1) {
// 记录准备分割、合并的起始位置
ListNode cur = dummyNode.next;
// 记录之前已合并完的链表结束位置
ListNode prev = dummyNode;
while (cur != null) {
// 第1个链表的头
ListNode head1 = curr;
// 取长度为subLength的子链表
for (int i = 1; i < subLength && cur.next != null; i++) {
cur = cur.next;
}
// 第2个链表的头
ListNode head2 = cur.next;
// 断开两个链表的连接
cur.next = null;
cur = head2;
// 取出第2个长度为subLength的子链表
for (int i = 1; i < subLength && cur != null; i++) {
cur = cur.next;
}
// 记录取出两个链表后剩下的链表位置
ListNode next = null;
if (cur != null) {
next = cur.next;
// 断开第二个子链表
cur.next = null;
}
// 将合并后的链表与已合并的部分连接上
prev.next =merge(head1, head2);
// 更新prev到新的合并后的链表结束位置
while (prev.next != null) {
prev = prev.next;
}
// 更新cur到未合并到链表开始位置
cur = next;
}
}
return dummyNode.next;
}
}
