【完虐算法】单链表的排序【完虐算法】单链表的排序

【【完虐算法】单链表的排序】更多算法题解，请关注公众号《程序员学长》
单链表的排序问题描述
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=dummyHeadwhile 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 = head2return 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 = 1while subLength < length:prev=dummyHead cur=dummyHead.nextwhile cur: #截取长度为subLength的子链表head1 head1 = cur for i in range(1, subLength): if cur.next: cur = cur.next else: breakhead2 = 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 * 2return dummyHead.next

该算法的时间复杂度是O(nlogn)，空间复杂度是O(1)。