leetcode解题-insertion sort list

class (object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        dummy = ListNode(0)
        dummy.next = head
        cur = head
        while cur.next:
            pre = dummy
            while pre != cur and pre.next.val < cur.next.val:
                pre = pre.next
            if pre == cur:
                cur = cur.next
            else:
                next = cur.next
                cur.next = cur.next.next
                next.next = pre.next
                pre.next = next
        return dummy.next

class (object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if not head:
            return head
        dummy = ListNode(0)
        dummy.next = head
        cur = head
        while cur.next:
            if cur.next.val < cur.val:
                pre = dummy
                while pre != cur and pre.next.val < cur.next.val:
                    pre = pre.next
                if pre == cur:
                    cur = cur.next
                else:
                    next = cur.next
                    cur.next = cur.next.next
                    next.next = pre.next
                    pre.next = next
            else:
                cur = cur.next
        return dummy.next