题解 | #单链表的排序#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        # write code here
        pre=head
        result_list=[]
        while pre:
            result_list.append(pre.val)
            pre=pre.next
        result_list.sort()  # 对列表排序的时间复杂度是nlogn
        dummy=ListNode(0)
        res=dummy
        for i in result_list:
            res.next=ListNode(i)
            res=res.next
        return dummy.next


            

把链表的值都加到list里边，然后对列表进行排序，list.sort()的时间复杂度是nlogn，最后虽然遍历了列表，但是这个时间复杂度忽略不计。最后在根据list重建链表。