链表实现

  1. def insertionSortList(head):
  2.    dummyhead = Node(0)
  3.    dummyhead.next=head
  4.    lastsorted = head
  5.    cur = head.next
  6.    while cur:
  7.        if cur.val>= lastsorted.val:
  8.            lastsorted=lastsorted.next
  9.        else:
  10.            pre =dummyhead
  11.            while pre.next.val<= cur.val:# 找到大于当前值的结点
  12.                pre=pre.next   # pre 是插入cur 的前一个位置
  13.            lastsorted.next=cur.next # 继承cur 后面的结点
  14.            cur.next = pre.next  # 继承pre后面的结点
  15.            pre.next =cur
  16.        cur=lastsorted.next # cur 是 原来cur.next
  17.    return  dummyhead