题解 | #单链表的排序#

# 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
        #  这必须借助数组
        num = []
        newListNode = ListNode(0)
        cur = newListNode
        if head == None:
            return head

        while head:
            num.append(head.val)
            head = head.next
        num.sort()
        # 创建新链表将数组中的值串接起来
        for i in range(len(num)):
            cur.next = ListNode(num[i])
            cur = cur.next
        return newListNode.next

解题思路：借助空数组排序很方便

首先定义一个空数组num = []

开始遍历链表将链表中的值依次填充至数组中，让后调用sort方法实现排序

定义一个新的链表 开始从数组中获取链表的值