链表插入排序

# Definition for singly-linked list. # class ListNode(object): # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution(object): def insertionSortList(self, head): """ :type head: ListNode :rtype: ListNode """ # 无节点和只有一个节点,直接返回 if(head==None or head.next==None): return head dummy = ListNode(0) dummy.next = head pre, cur = head, head.next while cur: # 如果cur的值比pre的值大，说明无需排序，cur=cur.next；pre=pre.next 开始下一个循环 if cur.val>pre.val: pre, cur= cur, cur.next continue # 如果cur的值比pre的值小，说明需要排序，此时pre.next指向cur.next pre.next = cur.next # 哑结点，始终指向新的头结点，直接返回哑结点.next h = dummy # 已排好序的h 指针一直往前走 while h.next.val<cur.val: h = h.next # 直接完成交换不用临时节点 cur.next = h.next h.next = cur cur = pre.next return dummy.next