python-leetcode 33.排序链表

题目：

给定链表的头结点head,请将其按升序排列，并返回排序后的链表

---

方法一：自顶向下归并排序

链表自顶向下归并排序的过程：

1.找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1 步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点

2.对两个链表进行排序

3.将两个排序后的子链表合并，得到完整的排序后的链表。可以使用[合并两个有序链表]的做法，将两个有序的子链表进行合并

可以通过递归实现。递归的终止条件是链表的节点个数小于或等于 1，即当链表为空或者链表只包含 1 个节点时，不需要对链表进行拆分和排序

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):def sortList(self, head):""":type head: Optional[ListNode]:rtype: Optional[ListNode]"""def sortFunc(head,tail):#个递归的排序函数,tail 是递归调用时用于控制链表的尾部的边界if not head: #链表已经空return headif head.next==tail: #当前链表只有一个元素，或者已经到达分割链表的边界head.next=Nonereturn headslow=fast=headwhile fast !=tail:slow=slow.nextfast=fast.nextif fast != tail:  #fast 每次走两步，slow 每次走一步fast=fast.nextmid=slow  #当 fast 到达链表尾部时，slow 就在链表的中间位置return merge(sortFunc(head,mid),sortFunc(mid,tail))
#递归调用sortFunc对head到mid的部分和mid到tail的部分分别进行排序，然后将两个排序好的部分合并。合并的过程交给 merge 函数def merge(head1,head2): #将两个已排序的链表合并成一个有序的链表dummyHead=ListNode(0) #虚拟的头节点temp,temp1,temp2=dummyHead,head1,head2
#临时指针，用来构建最终合并的链表,两个已排序链表的头节点while temp1 and temp2: #同时遍历temp1和temp2，比较它们的值，并将较小的节点连接到 temp 上，直到其中一个链表遍历完if temp1.val<temp2.val:temp.next=temp1  #将 temp1 加入合并后的链表temp1=temp1.next #将 temp1 移动到下一个节点else:temp.next=temp2temp2=temp2.nexttemp=temp.next  #将已合并链表的指针后移if temp1:  #如果 temp1 链表剩余节点未合并完，则直接将剩余的节点连接temp.next=temp1elif temp2:  #如果 temp2 链表剩余节点未合并完，同样将剩余的节点连接到temp.next=temp2return dummyHead.next  #去除虚拟结点，返回合并后的链表的头节点return sortFunc(head,None) #sortList 函数通过调用 sortFunc 来对整个链表进行排序，None 作为 tail 的参数表示没有上限

时间复杂度：O(nlogn)

空间复杂度：O(nlogn)

---

方法二：自底向上归并排序

首先求得链表的长度 length，然后将链表拆分成子链表进行合并。

具体做法：

1. 用 subLength 表示每次需要排序的子链表的长度，初始时 subLength=1。

2. 每次将链表拆分成若干个长度为 subLength 的子链表（最后一个子链表的长度可以小于 subLength）按照每两个子链表一组进行合并，合并后即可得到若干个长度为subLength×2 的有序子链表（最后一个子链表的长度可以小于 subLength×2）。合并两个子链表仍然使用[合并两个有序链表]的做法。

3. 将 subLength 的值加倍，重复第 2 步，对更长的有序子链表进行合并操作，直到有序子链表的长度大于或等于 length，整个链表排序完毕。        

举例： 

首先，归并长度为 1 的子链表。例如 [4,2,1,3]，把第一个节点和第二个节点归并，第三个节点和第四个节点归并，得到 [2,4,1,3]。
然后，归并长度为 2 的子链表。例如 [2,4,1,3]，把前两个节点和后两个节点归并，得到 [1,2,3,4]。
然后，归并长度为 4 的子链表。
依此类推，直到归并的长度大于等于链表长度为止，此时链表已经是有序的了。

初始链表: 4 -> 2 -> 1 -> 3

step = 1:
- 分割: [4], [2], [1], [3]
- 合并: [2 -> 4], [1 -> 3]
- 结果: 2 -> 4 -> 1 -> 3

step = 2:
- 分割: [2 -> 4], [1 -> 3]
- 合并: [1 -> 2 -> 3 -> 4]
- 结果: 1 -> 2 -> 3 -> 4

step = 4:
- 分割: [1 -> 2 -> 3 -> 4]
- 无需合并
- 结果: 1 -> 2 -> 3 -> 4

最终结果: 1 -> 2 -> 3 -> 4

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = nextclass Solution(object):# 获取链表长度def getListLength(self, head):length = 0while head:length += 1head = head.nextreturn length# 分割链表# 如果链表长度 <= size，不做任何操作，返回空节点# 如果链表长度 > size，把链表的前 size 个节点分割出来（断开连接），并返回剩余链表的头节点def splitList(self, head, size):# 先找到 next_head 的前一个节点cur = headfor _ in range(size - 1):if cur is None:breakcur = cur.next# 如果链表长度 <= sizeif cur is None or cur.next is None:return None  # 不做任何操作，返回空节点next_head = cur.nextcur.next = None  # 断开 next_head 的前一个节点和 next_head 的连接return next_head# 合并两个有序链表（双指针）# 返回合并后的链表的头节点和尾节点def mergeTwoLists(self, list1, list2):cur = dummy = ListNode()  # 用哨兵节点简化代码逻辑while list1 and list2:if list1.val < list2.val:cur.next = list1  # 把 list1 加到新链表中list1 = list1.nextelse:  # 注：相等的情况加哪个节点都是可以的cur.next = list2  # 把 list2 加到新链表中list2 = list2.nextcur = cur.nextif list1:cur.next=list1elif list2:cur.next=list2while cur.next:cur=cur.nextreturn dummy.next, curdef sortList(self, head):length = self.getListLength(head)  # 获取链表长度dummy = ListNode(next=head)  # 用哨兵节点简化代码逻辑step = 1  # 步长（参与合并的链表长度）while step < length:new_list_tail = dummy  # 新链表的末尾cur = dummy.next  # 每轮循环的起始节点while cur:# 从 cur 开始，分割出两段长为 step 的链表，头节点分别为 head1 和 head2head1 = curhead2 = self.splitList(head1, step)cur = self.splitList(head2, step)  # 下一轮循环的起始节点# 合并两段长为 step 的链表head, tail = self.mergeTwoLists(head1, head2)# 合并后的头节点 head，插到 new_list_tail 的后面new_list_tail.next = headnew_list_tail = tail  # tail 现在是新链表的末尾step *= 2return dummy.next

时间复杂度：O(logn) 

空间复杂度：O(1)

方法一的归并是自顶向下计算，需要 O(logn) 的递归栈开销。

方法二将其改成自底向上计算，空间复杂度优化成 O(1)

                                                                                                        源自力扣官方题解，灵茶山艾府