单链表的排序（python）

标签：head 单链 nums python 链表 遍历 数组 排序

思路：

链表最难受的就是不能按照下标访问，只能逐个遍历，那像排序中常规的快速排序、堆排序都不能用了，只能用依次遍历的冒泡排序、选择排序这些。但是这些O(n2)O(n^2)O(n2)复杂度的排序方法太费时间了，我们可以将其转化成数组后再排序。

具体做法：

• step 1：遍历链表，将节点值加入数组。
• step 2：使用内置的排序函数对数组进行排序。
• step 3：依次遍历数组和链表，按照位置将链表中的节点值修改为排序后的数组值。

def sortInList(self , head: ListNode) -> ListNode:         # write code here         p = head         nums = []         #遍历链表，将节点值加入数组         while p:             nums.append(p.val)             p = p.next         p = head         #对数组元素排序         nums.sort()         #遍历数组         for i in range(len(nums)):             #将数组元素依次加入链表             p.val = nums[i]             p = p.next         return head

标签：head,单链,nums,python,链表,遍历,数组,排序
From： https://www.cnblogs.com/ailie/p/16941770.html