题解 | #单链表的排序#

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围：0<n≤100000 要求：空间复杂度 O(n)，时间复杂度O(nlogn)

解法：递归分治归并排序，递归将head切成两个列表head1和head2，到最后不能再切（即head内只有一个元素），head1和head2只有一个元素的时候合并head1和head2，合并后的head是有序的，一直往上head1和head2一直有序

上一个题目是合并两个有序链表，我直接拿上一个题目的算法直接用了

我自己写的话复杂度应该可能是n(n-1)/2，自己写的话，会新定义一个list，将head种最小的截出来，放入list结尾，复杂度为1+2+……+n-1，或者冒泡排序，最后看了评论才知道这个算法

```# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
    @staticmethod
    def Merge(pHead1, pHead2):
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        node1 = pHead1
        node2 = pHead2
        result = pHead1
        if node1.val > node2.val:
            result = pHead2
            node2 = node2.next
        else :
            node1 = node1.next
        current_node = result
        while ((node1 != None) and (node2 != None)):
            if (node1.val <= node2.val):
                current_node.next = node1
                node1 = node1.next
            else:
                current_node.next = node2
                node2 = node2.next
            current_node = current_node.next
        if node2 != None:
            current_node.next = node2
        elif node1 != None:
            current_node.next = node1
        return result

    def sortInList(self , head: ListNode) -> ListNode:
        if head == None:
            return head
        if head.next == None:
            return head
        fast = head.next
        slow = head
        while fast != None:
            if fast.next == None:
                break
            slow = slow.next
            fast = fast.next.next
        head2 = slow.next
        slow.next = None
        head1 = self.sortInList(head)
        head2 = self.sortInList(head2)
        head = self.Merge(head1,head2)
        return head