对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
来源：力扣（LeetCode）
直接sort()
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def insertionSortList(self, head: ListNode) -> ListNode: res=head nodes=[] while res: nodes.append(res.val) res=res.next nodes.sort() i=0 res=head while res: res.val=nodes[i] res=res.next i+=1 return head
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def insertionSortList(self, head: ListNode) -> ListNode: if not head:return None nodes=[] node=head while node: nodes.append(node) node=node.next nodes=sorted(nodes,key=lambda x:x.val) for i in range(len(nodes)-1): nodes[i].next=nodes[i+1] nodes[len(nodes)-1].next=None return nodes[0]
堆
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None import heapq class Solution: def insertionSortList(self, head: ListNode) -> ListNode: if not head: return head heap = [] heapq.heapify(heap) while head: heapq.heappush(heap, head.val) head = head.next root = ListNode(0) cur = root while heap: val = heapq.heappop(heap) cur.next = ListNode(val) cur = cur.next return root.next
归并排序
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def insertionSortList(self, head: ListNode) -> ListNode: def merge(p1, p2): p = helper = ListNode() while p1 and p2: if p1.val < p2.val: p.next = p1 p1 = p1.next else: p.next = p2 p2 = p2.next p = p.next if p1: p.next = p1 if p2: p.next = p2 return helper.next def merge_sort(left, right): if left is right: return left slow, fast = left, left.next while fast and fast.next: slow, fast = slow.next, fast.next.next mid, slow.next = slow.next, None p1 = merge_sort(left, slow) p2 = merge_sort(mid, right) return merge(p1, p2) return merge_sort(head, None)
插入排序
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def insertionSortList(self, head: ListNode) -> ListNode: dummy=ListNode(0) while head: p=dummy while p.next and p.next.val<head.val: p=p.next q=head head=head.next q.next=p.next p.next=q return dummy.next