题解 | #单链表的排序#

# 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
        if head is None or head.next is None:   #特殊值处理
            return head

        l = []  #保存节点和节点数值，后面排序会用
        p = head    #遍历链表指针

        while p:     
            l.append([p,p.val])  #将节点p和p的值放到l中
            p = p.next

        l.sort(key=lambda x:x[1])  #按照l第二个元素（节点值）排序

        for i in range(len(l)):   #将l[i][0]节点对象串联起来
            if i < len(l) -1:       #注意最后一个节点的next赋给None
                l[i][0].next = l[i+1][0]
            else:
                l[i][0].next = None
        
        return l[0][0] # 返回l的第一个节点l[0][0]