LeetCode-148：排序链表
【摘要】
题目描述：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
思路分析： ...
题目描述：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例： 输入：head = [4,2,1,3] 输出：[1,2,3,4]
思路分析：
方法一：自顶向下归并排序
对链表自顶向下归并排序的过程如下。
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 22 步，慢指针每次移动 11 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。
- 对两个子链表分别排序。
- 将两个排序后的子链表合并，得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法，将两个有序的子链表进行合并。
- 上述过程可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 11，即当链表为空或者链表只包含 11 个节点时，不需要对链表进行拆分和排序。
java实现哎：
-
class Solution {
-
public ListNode sortList(ListNode head) {
-
return sortList(head, null);
-
}
-
-
public ListNode sortList(ListNode head, ListNode tail) {
-
if (head == null) {
-
return head;
-
}
-
if (head.next == tail) {
-
head.next = null;
-
return head;
-
}
-
ListNode slow = head, fast = head;
-
while (fast != tail) {
-
slow = slow.next;
-
fast = fast.next;
-
if (fast != tail) {
-
fast = fast.next;
-
}
-
}
-
ListNode mid = slow;
-
ListNode list1 = sortList(head, mid);
-
ListNode list2 = sortList(mid, tail);
-
ListNode sorted = merge(list1, list2);
-
return sorted;
-
}
-
-
public ListNode merge(ListNode head1, ListNode head2) {
-
ListNode dummyHead = new ListNode(0);
-
ListNode temp = dummyHead, temp1 = head1, 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;
-
}
-
}
复杂度分析：
时间复杂度：O(n \log n)O(nlogn)，其中 nn 是链表的长度。
空间复杂度：O(\log n)O(logn)，其中 nn 是链表的长度。空间复杂度主要取决于递归调用的栈空间
方法二：自底向上归并排序
使用自底向上的方法实现归并排序，则可以达到 O(1)O(1) 的空间复杂度。
首先求得链表的长度 \textit{length}length，然后将链表拆分成子链表进行合并。
具体做法如下。
- 用 subLength 表示每次需要排序的子链表的长度，初始时subLength=1。
- 每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于subLength），按照每两个子链表一组进行合并，合并后即可得到若干个长度为 subLength×2 的有序子链表（最后一个子链表的长度可以小于subLength×2）。合并两个子链表仍然使用「21. 合并两个有序链表」的做法。
- 将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。
- 如何保证每次合并之后得到的子链表都是有序的呢？可以通过数学归纳法证明。
- 初始时 subLength=1，每个长度为 11 的子链表都是有序的。
- 如果每个长度为 subLength 的子链表已经有序，合并两个长度为 subLength 的有序子链表，得到长度为subLength×2 的子链表，一定也是有序的。
- 当最后一个子链表的长度小于 subLength 时，该子链表也是有序的，合并两个有序子链表之后得到的子链表一定也是有序的。
因此可以保证最后得到的链表是有序的。
java实现：
-
class Solution {
-
// 自底向上归并排序
-
public ListNode sortList(ListNode head) {
-
if(head == null){
-
return head;
-
}
-
-
// 1. 首先从头向后遍历,统计链表长度
-
int length = 0; // 用于统计链表长度
-
ListNode node = head;
-
while(node != null){
-
length++;
-
node = node.next;
-
}
-
-
// 2. 初始化 引入dummynode
-
ListNode dummyHead = new ListNode(0);
-
dummyHead.next = head;
-
-
// 3. 每次将链表拆分成若干个长度为subLen的子链表 , 并按照每两个子链表一组进行合并
-
for(int subLen = 1;subLen < length;subLen <<= 1){ // subLen每次左移一位（即sublen = sublen*2） PS:位运算对CPU来说效率更高
-
ListNode prev = dummyHead;
-
ListNode curr = dummyHead.next; // curr用于记录拆分链表的位置
-
-
while(curr != null){ // 如果链表没有被拆完
-
// 3.1 拆分subLen长度的链表1
-
ListNode head_1 = curr; // 第一个链表的头 即 curr初始的位置
-
for(int i = 1; i < subLen && curr != null && curr.next != null; i++){ // 拆分出长度为subLen的链表1
-
curr = curr.next;
-
}
-
-
// 3.2 拆分subLen长度的链表2
-
ListNode head_2 = curr.next; // 第二个链表的头 即 链表1尾部的下一个位置
-
curr.next = null; // 断开第一个链表和第二个链表的链接
-
curr = head_2; // 第二个链表头 重新赋值给curr
-
for(int i = 1;i < subLen && curr != null && curr.next != null;i++){ // 再拆分出长度为subLen的链表2
-
curr = curr.next;
-
}
-
-
// 3.3 再次断开 第二个链表最后的next的链接
-
ListNode next = null;
-
if(curr != null){
-
next = curr.next; // next用于记录 拆分完两个链表的结束位置
-
curr.next = null; // 断开连接
-
}
-
-
// 3.4 合并两个subLen长度的有序链表
-
ListNode merged = mergeTwoLists(head_1,head_2);
-
prev.next = merged; // prev.next 指向排好序链表的头
-
while(prev.next != null){ // while循环 将prev移动到 subLen*2 的位置后去
-
prev = prev.next;
-
}
-
curr = next; // next用于记录 拆分完两个链表的结束位置
-
}
-
}
-
// 返回新排好序的链表
-
return dummyHead.next;
-
}
-
-
-
// 此处是Leetcode21 --> 合并两个有序链表
-
public ListNode mergeTwoLists(ListNode l1,ListNode l2){
-
ListNode dummy = new ListNode(0);
-
ListNode curr = dummy;
-
-
while(l1 != null && l2!= null){ // 退出循环的条件是走完了其中一个链表
-
// 判断l1 和 l2大小
-
if (l1.val < l2.val){
-
// l1 小 ， curr指向l1
-
curr.next = l1;
-
l1 = l1.next; // l1 向后走一位
-
}else{
-
// l2 小 ， curr指向l2
-
curr.next = l2;
-
l2 = l2.next; // l2向后走一位
-
}
-
curr = curr.next; // curr后移一位
-
}
-
-
// 退出while循环之后,比较哪个链表剩下长度更长,直接拼接在排序链表末尾
-
if(l1 == null) curr.next = l2;
-
if(l2 == null) curr.next = l1;
-
-
// 最后返回合并后有序的链表
-
return dummy.next;
-
}
-
}
复杂度分析
-
时间复杂度：O(n \log n)O(nlogn)，其中 nn 是链表的长度。
-
空间复杂度：O(1)O(1)。
文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/xiewenrui1996/article/details/113397919
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）