# LeetCode 148、排序链表
# 一、题目描述
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。示例 1：
img
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
img
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
- 链表中节点的数目在范围
[0, 5 * 10^4]内 -10^5 <= Node.val <= 10^5
**进阶：**你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
# 二、题目解析
题目要求时间空间复杂度分别为 O(nlogn) 和 O(1) ，根据时间复杂度和题目中的排序两个字，可以联想到归并排序和快速排序。
所以，本题有两种解法：归并排序和快速排序。
这里我们先用归并排序的思路进行处理，其中合并的基本操作如下：
- 1、长度为 1 的链表和长度为 1 的链表合并后，形成一个长度为 2 的链表
- 2、长度为 2 的链表和长度为 2 的链表合并后，形成一个长度为 4 的链表
- 。。。
而由于合并过程中操作的是链表，所以需要有断链和重新连接的过程。
具体操作步骤如下：
1、先获取链表长度，基于这个长度才能知道后续合并到什么时候截止
2、设置三个指针 prev、 curr、 next。
其中， prev表示已经排序好的链表的【尾节点】。
curr 一开始设置为准备排序的那些节点的【首节点】，然后向后移动，获取相应的节点，到达所有正在准备排序的那些节点的【尾节点】位置。
next 表示接下来需要排序的那些节点的【首节点】。
3、断开 prev 与 curr 的连接，再断开 curr 与 next 的连接。
4、把 curr 访问的这些节点划分为两个区域，区域的长度取决于此时进行到了长度为多少的链表进行合并操作，一个是左链表，一个是右链表，把这两个链表进行合并操作。
5、合并成功之后，prev 移动到尾部，curr 来到 next 的位置，继续后面的归并操作。
6、这样一轮下来，已经把长度为 2 的链表和长度为 2 的链表合并，形成了一个长度为 4 的链表。
7、接下来，只需要执行上述同样的操作，唯一的修改点在于合并的子链表长度变成了 4。
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 排序链表（LeetCode 148）：https://leetcode.cn/problems/sort-list/
class Solution {
public ListNode sortList(ListNode head) {
// 获链表的总长度
int length = 0;
// 从链表的头节点开始访问
ListNode node = head;
// 利用 while 循环，可以统计出链表的节点个数，即长度
while (node != null) {
length++;
node = node.next;
}
// 在原链表的头部设置一个虚拟头节点
// 因为可能会操作到原链表的头节点
// 设置了虚拟头节点后，原链表的头节点和原链表的其它节点地位一样
ListNode dummyHead = new ListNode(0, head);
// 利用 for 循环，执行合并的操作
// 长度为 1 的链表和长度为 1 的链表合并后，形成一个长度为 2 的链表
// 长度为 2 的链表和长度为 2 的链表合并后，形成一个长度为 4 的链表
// 长度为 4 的链表和长度为 4 的链表合并后，形成一个长度为 8 的链表
// 长度为 8 的链表和长度为 8 的链表合并后，形成一个长度为 16 的链表
// 也有可能是，长度为 8 的链表和长度为 5 的链表合并后，形成一个长度为 13 的链表
// 但是，每次合并过程中，子链表都会想要扩充为原来的两倍
// 直到子链表想要扩充的长度超过了 length
for (int subLength = 1; subLength < length; subLength *= 2) {
// 整个归并过程分为三个步骤
// 1、不停的划分，直到无法划分为止
// 2、开始两两合并
// 3、每次合并之后的结果都需要连接起来
// 每次都把结果连接到 dummyHead，因此先记录一下
// prev 表示已经排序好的链表的【尾节点】
ListNode prev = dummyHead;
// dummyHead 的后面节点才是原链表的节点，需要把它们进行划分
// curr 表示所有正在准备排序的那些节点的【尾节点】
ListNode curr = dummyHead.next;
// 利用 while 循环，寻找出每次划分后子链表的头节点
while (curr != null) {
// 每次都是两个子链表开始合并
// 1、先寻找出【左子链表】，长度为 subLength
ListNode head1 = curr;
// 通过 for 循环，找出 subLength 个节点来
// curr 的索引为 0 ，需要再找 subLength - 1 个节点来
for (int i = 1; i < subLength && curr.next != null; i++) {
curr = curr.next;
}
// 2、再寻找出【右子链表】，长度最多为 subLength，甚至有可能长度为 0
ListNode head2 = curr.next;
// 此时，需要将【左子链表】与【右子链表】的连接断开
curr.next = null;
// curr 来到【右子链表】的头部
curr = head2;
// 通过 for 循环，找出【右子链表】的那些节点来
// 【右子链表】的节点个数可能达不到 subLength，甚至只有 1 个或者 0 个节点
for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
curr = curr.next;
}
// 获取到【右子链表】之后，需要把它和后续链表断开
// next 表示接下来需要排序的那些节点的【首节点】
ListNode next = null;
// 如果 curr != null，那么说明【右子链表】的节点个数达到了 subLength 个，并且后续还有节点
if (curr != null) {
// 记录一下后面节点
next = curr.next;
// 再将【右子链表】和后续链表断开
curr.next = null;
}
// 将【左子链表】与【右子链表】合并
ListNode merged = mergeTwoLists(head1, head2);
// 合并之后的结果需要连接到前一个链表
prev.next = merged;
// prev 来到链表的尾部，是下一个即将合成链表之后的前一个链表的尾节点
while (prev.next != null) {
prev = prev.next;
}
// curr 来到 next，处理后面的节点
curr = next;
}
}
return dummyHead.next;
}
// 合并两个有序链表的代码
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
ListNode dummy = new ListNode(-1);
// 设置一个指针，指向虚拟节点
ListNode pre = dummy;
// 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
while (l1 != null && l2 != null) {
// 如果 l1 当前节点的值小于等于了 l2 当前节点的值
if (l1.val <= l2.val) {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l1
pre.next = l1;
// 让 l1 向后移动
l1 = l1.next;
}else {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l2
pre.next =l2;
// 让 l2 向后移动
l2 = l2.next;
}
// 让 pre 向后移动
pre = pre.next;
}
// 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
// 直接把剩下的节点加入到 pre 的 next 指针位置
// 如果 l1 中还有节点
if (l1 != null) {
// 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l1;
}
// 如果 l2 中还有节点
if (l2 != null) {
// 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l2;
}
// 最后返回虚拟节点的 next 指针
return dummy.next;
}
}
# 2、C++ 代码
class Solution {
public:
ListNode* sortList(ListNode* head) {
// 获链表的总长度
int length = 0;
// 从链表的头节点开始访问
ListNode* node = head;
// 利用 while 循环，可以统计出链表的节点个数，即长度
while (node != NULL) {
length++;
node = node->next;
}
// 在原链表的头部设置一个虚拟头节点
// 因为可能会操作到原链表的头节点
// 设置了虚拟头节点后，原链表的头节点和原链表的其它节点地位一样
ListNode* dummyHead = new ListNode(0, head);
// 利用 for 循环，执行合并的操作
// 长度为 1 的链表和长度为 1 的链表合并后，形成一个长度为 2 的链表
// 长度为 2 的链表和长度为 2 的链表合并后，形成一个长度为 4 的链表
// 长度为 4 的链表和长度为 4 的链表合并后，形成一个长度为 8 的链表
// 长度为 8 的链表和长度为 8 的链表合并后，形成一个长度为 16 的链表
// 也有可能是，长度为 8 的链表和长度为 5 的链表合并后，形成一个长度为 13 的链表
// 但是，每次合并过程中，子链表都会想要扩充为原来的两倍
// 直到子链表想要扩充的长度超过了 length
for (int subLength = 1; subLength < length; subLength = 2) {
// 整个归并过程分为三个步骤
// 1、不停的划分，直到无法划分为止
// 2、开始两两合并
// 3、每次合并之后的结果都需要连接起来
// 每次都把结果连接到 dummyHead，因此先记录一下
// prev 表示已经排序好的链表的【尾节点】
ListNode prev = dummyHead;
// dummyHead 的后面节点才是原链表的节点，需要把它们进行划分
// curr 表示所有正在准备排序的那些节点的【尾节点】
ListNode* curr = dummyHead->next;
// 利用 while 循环，寻找出每次划分后子链表的头节点
while (curr != NULL) {
// 每次都是两个子链表开始合并
// 1、先寻找出【左子链表】，长度为 subLength
ListNode* head1 = curr;
// 通过 for 循环，找出 subLength 个节点来
// curr 的索引为 0 ，需要再找 subLength - 1 个节点来
for (int i = 1; i < subLength && curr->next != NULL; i++) {
curr = curr->next;
}
// 2、再寻找出【右子链表】，长度最多为 subLength，甚至有可能长度为 0
ListNode* head2 = curr->next;
// 此时，需要将【左子链表】与【右子链表】的连接断开
curr->next = NULL;
// curr 来到【右子链表】的头部
curr = head2;
// 通过 for 循环，找出【右子链表】的那些节点来
// 【右子链表】的节点个数可能达不到 subLength，甚至只有 1 个或者 0 个节点
for (int i = 1; i < subLength && curr != NULL && curr->next != NULL; i++) {
curr = curr->next;
}
// 获取到【右子链表】之后，需要把它和后续链表断开
//->next 表示接下来需要排序的那些节点的【首节点】
ListNode* next = NULL;
// 如果 curr != NULL，那么说明【右子链表】的节点个数达到了 subLength 个，并且后续还有节点
if (curr != NULL) {
// 记录一下后面节点
next = curr->next;
// 再将【右子链表】和后续链表断开
curr->next = NULL;
}
// 将【左子链表】与【右子链表】合并
ListNode* merged = mergeTwoLists(head1, head2);
// 合并之后的结果需要连接到前一个链表
prev->next = merged;
// prev 来到链表的尾部，是下一个即将合成链表之后的前一个链表的尾节点
while (prev->next != NULL) {
prev = prev->next;
}
// curr 来到 next，处理后面的节点
curr = next;
}
}
return dummyHead->next;
}
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
ListNode *dummy = new ListNode(-1);
// 设置一个指针，指向虚拟节点
ListNode *pre = dummy;
// 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
while (l1 != NULL && l2 != NULL) {
// 如果 l1 当前节点的值小于等于了 l2 当前节点的值
if (l1->val <= l2->val) {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l1
pre->next = l1;
// 让 l1 向后移动
l1 = l1->next;
}else {
// 让 pre 指向节点的 next 指针指向这个更小值的节点
// 即指向 l2
pre->next =l2;
// 让 l2 向后移动
l2 = l2->next;
}
// 让 pre 向后移动
pre = pre->next;
}
// 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
// 直接把剩下的节点加入到 pre 的 next 指针位置
// 如果 l1 中还有节点
if (l1 != NULL) {
// 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
pre->next = l1;
}
// 如果 l2 中还有节点
if (l2 != NULL) {
// 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
pre->next = l2;
}
// 最后返回虚拟节点的 next 指针
return dummy->next;
}
};
# 3、Python 代码
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 获链表的总长度
length = 0
# 从链表的头节点开始访问
node = head
# 利用 while 循环，可以统计出链表的节点个数，即长度
while node :
length += 1
node = node.next
# 在原链表的头部设置一个虚拟头节点
# 因为可能会操作到原链表的头节点
# 设置了虚拟头节点后，原链表的头节点和原链表的其它节点地位一样
dummyHead = ListNode(0)
dummyHead.next = head
# 利用 for 循环，执行合并的操作
# 长度为 1 的链表和长度为 1 的链表合并后，形成一个长度为 2 的链表
# 长度为 2 的链表和长度为 2 的链表合并后，形成一个长度为 4 的链表
# 长度为 4 的链表和长度为 4 的链表合并后，形成一个长度为 8 的链表
# 长度为 8 的链表和长度为 8 的链表合并后，形成一个长度为 16 的链表
# 也有可能是，长度为 8 的链表和长度为 5 的链表合并后，形成一个长度为 13 的链表
# 但是，每次合并过程中，子链表都会想要扩充为原来的两倍
# 直到子链表想要扩充的长度超过了 length
subLength = 1
while subLength < length :
# 整个归并过程分为三个步骤
# 1、不停的划分，直到无法划分为止
# 2、开始两两合并
# 3、每次合并之后的结果都需要连接起来
# 每次都把结果连接到 dummyHead，因此先记录一下
# prev 表示已经排序好的链表的【尾节点】
prev = dummyHead
# dummyHead 的后面节点才是原链表的节点，需要把它们进行划分
# curr 表示所有正在准备排序的那些节点的【尾节点】
curr = dummyHead.next
# 利用 while 循环，寻找出每次划分后子链表的头节点
while curr :
# 每次都是两个子链表开始合并
# 1、先寻找出【左子链表】，长度为 subLength
head1 = curr
# 通过 for 循环，找出 subLength 个节点来
# curr 的索引为 0 ，需要再找 subLength - 1 个节点来
for i in range( 1 , subLength ) :
if curr.next:
curr = curr.next
# 2、再寻找出【右子链表】，长度最多为 subLength，甚至有可能长度为 0
head2 = curr.next
# 此时，需要将【左子链表】与【右子链表】的连接断开
curr.next = None
# curr 来到【右子链表】的头部
curr = head2
# 通过 for 循环，找出【右子链表】的那些节点来
# 【右子链表】的节点个数可能达不到 subLength，甚至只有 1 个或者 0 个节点
for i in range( 1 , subLength ) :
if curr and curr.next:
curr = curr.next
# 获取到【右子链表】之后，需要把它和后续链表断开
# next 表示接下来需要排序的那些节点的【首节点】
nextNode = None
# 如果 curr != None，那么说明【右子链表】的节点个数达到了 subLength 个，并且后续还有节点
if curr :
# 记录一下后面节点
nextNode = curr.next
# 再将【右子链表】和后续链表断开
curr.next = None
# 将【左子链表】与【右子链表】合并
merged = self.mergeTwoLists(head1, head2)
# 合并之后的结果需要连接到前一个链表
prev.next = merged
# prev 来到链表的尾部，是下一个即将合成链表之后的前一个链表的尾节点
while prev.next :
prev = prev.next
# curr 来到 next，处理后面的节点
curr = nextNode
subLength = subLength * 2
return dummyHead.next
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
# 一开始设置一个虚拟节点，它的值为 -1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
dummy = ListNode(-1)
# 设置一个指针，指向虚拟节点
pre = dummy
# 通过一个循环，不断的比较 l1 和 l2 中当前节点值的大小，直到 l1 或者 l2 遍历完毕为止
while l1 and l2:
# 如果 l1 当前节点的值小于等于了 l2 当前节点的值
if l1.val <= l2.val :
# 让 pre 指向节点的 next 指针指向这个更小值的节点
# 即指向 l1
pre.next = l1
# 让 l1 向后移动
l1 = l1.next
else:
# 让 pre 指向节点的 next 指针指向这个更小值的节点
# 即指向 l2
pre.next =l2
# 让 l2 向后移动
l2 = l2.next
# 让 pre 向后移动
pre = pre.next
# 跳出循环后，l1 或者 l2 中可能有剩余的节点没有被观察过
# 直接把剩下的节点加入到 pre 的 next 指针位置
# 如果 l1 中还有节点
if l1 != None :
# 把 l1 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l1
# 如果 l2 中还有节点
if l2 != None :
# 把 l2 中剩下的节点全部加入到 pre 的 next 指针位置
pre.next = l2;
# 最后返回虚拟节点的 next 指针
return dummy.next
# 四、复杂度分析
时间复杂度：O(nlogn)
**空间复杂度：**O(1)