【问题】

Sort a linked list using insertion sort.

【代码】

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        if head == None or head.next == None:
    		return head
    	dummy = ListNode(0)
    	dummy.next = head
    	cur = head
    	while cur.next != None:
    		if cur.next.val < cur.val:
    			pre = dummy
    			while pre.next.val < cur.next.val:
    				pre = pre.next
    			temp = cur.next
    			cur.next = temp.next
    			temp.next = pre.next
    			pre.next = temp
    		else:
    			cur = cur.next
    	return dummy.next