Insertion Sort List

和数组的插入排序不一样，linked list的排序都很麻烦，这道题的插入排序不能使用从当前点往回寻找位置的方法了，因为单链表做不到这件事，所以我们只能另开一个链表，将之前排序好的点都放在上面，然后每次从头查找当前点应该放的位置，这题很容易TLE，有些点的next指针必须要清空

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode('d')
        while head:
            cur = dummy
            while cur.next and cur.next.val <= head.val:
                cur = cur.next
            nextNode = head.next
            head.next = cur.next
            cur.next = head
            head = nextNode
        return dummy.next