共计 2371 个字符，预计需要花费 6 分钟才能阅读完成。
更多算法题解，请关注公众号《程序员学长》
单链表的排序
问题形容
LeetCode 148. 排序链表
给定一个节点数为 n 的无序单链表，对其按升序排序。
要求：空间复杂度 O(n)，工夫复杂度 O(nlogn)。
示例：
输出：[-1,0,-2]
返回值：{-2,-1,0}
剖析问题
因为题目要求工夫复杂度是 O(nlogn)，那工夫复杂度是 O(nlogn) 的排序算法有归并排序、疾速排序和堆排序，其中最适宜链表的排序算法是归并排序。
归并排序是基于分治思维，最容易想到的就是自顶向下的递归实现。自顶向下的递归实现次要包含二个环节。
-
宰割环节
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点能够应用快慢指针法，快指针每次挪动 2 步，慢指针每次挪动 1 步，当快指针走到链表的开端时，慢指针恰好指向了链表的中点地位。
- 找到中点后，将链表在中点处宰割成两个子链表。
- 而后递归的进行宰割，直到宰割后的链表只有一个节点或者为 Null。这时，宰割的子链表都是有序的，因为只蕴含一个节点。
-
合并环节
- 将两个有序的链表合并成一个有序链表。咱们能够采纳双指针法求解。
- 递归执行，直到合并实现。
class Solution:
def sortList(self, head):
#如果链表为空或者只蕴含一个节点，递归终止
if not head or not head.next:
return head
#应用快慢指针法来寻找链表的中点
slow=head
fast=head.next
while fast and fast.next:
fast=fast.next.next
slow=slow.next
#slow 指向的就是链表的中点，将链表在中点处进行宰割
head2=slow.next
slow.next=None
#递归的切割宰割链表
left = self.sortList(head)
right = self.sortList(head2)
#合并链表，应用双指针法
tmp = res = ListNode(0)
while left and right:
if left.val < right.val:
tmp.next=left
left=left.next
else:
tmp.next=right
right=right.next
tmp=tmp.next
if left:
tmp.next=left
else:
tmp.next=right
return res.next该算法的工夫复杂度是 O(n)。因为自顶向下是通过递归来实现的，如果思考递归调用栈的栈空间，那么该算法的空间复杂度是 O(logn)。
优化
咱们也能够采纳自底向上的办法来求解。
首先，咱们求出链表的长度 length。而后将链表拆分成子链表进行合并。
- 咱们用 sublength 示意每次须要排序的子链表的长度，初始时 sublength=1。
- 每次将链表拆分成若干个长度为 sublength 的子链表（最初一个子链表的长度可能小于 sublength），依照每两个子链表一组进行合并，合并后即能够失去若干个长度为 sublength 2 的有序子链表（最初一个子链表的长度可能小于 sublength 2）。
- 将 sublength 的值加倍，反复第二步，而后对更长的有序子链表进行合并，直到有序子链表的长度大于或等于链表的长度，这样整个链表的排序就实现了。
咱们来看一下代码的实现。
class Solution:
def sortList(self, head):
#合并两个有序链表
def merge(head1, head2):
#哨兵节点
dummyHead = ListNode(0)
temp=dummyHead
while head1 and head2:
if head1.val <= head2.val:
temp.next = head1
head1 = head1.next
else:
temp.next = head2
head2 = head2.next
temp = temp.next
if head1:
temp.next = head1
else:
temp.next = head2
return dummyHead.next
#如果链表为空，间接返回
if not head:
return head
#遍历一遍链表，求出链表的长度
length = 0
node = head
while node:
length += 1
node = node.next
#创立一个哨兵节点, 指向链表头
dummyHead = ListNode(0)
dummyHead.next=head
#初始时，子链表的长度为 1
subLength = 1
while subLength < length:
prev=dummyHead
cur=dummyHead.next
while cur:
#截取长度为 subLength 的子链表 head1
head1 = cur
for i in range(1, subLength):
if cur.next:
cur = cur.next
else:
break
head2 = cur.next
cur.next = None
#截取长度为 subLength 的子链表 head2
cur = head2
for i in range(1, subLength):
if cur and cur.next:
cur = cur.next
else:
break
#截取完后残余的链表节点
surplus_head = None
if cur:
surplus_head = cur.next
cur.next = None
#将两个有序链表进行合并
merged = merge(head1, head2)
#将排好序的链表插入到新生成的链表里
prev.next = merged
#将指针挪动到链表的开端
while prev.next:
prev = prev.next
#持续合并残余的节点
cur=surplus_head
subLength = subLength * 2
return dummyHead.next该算法的工夫复杂度是 O(nlogn)，空间复杂度是 O(1)。
正文完
