LeetCode 147：LinkedList Insertion Sort

这里有两种方法，第一种是我的，2000+ms，第二种是sample code，100+ms，没找到两种方法大的区别在哪里，可是performance怎么差这么大？
跪求大佬讲解。


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

class Solution(object):

    # Slow, 2000+ms
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return head

        newHead = ListNode(0)
        newHead.next = head
        head = head.next
        newHead.next.next = None
        while head is not None:
            postNode = newHead.next
            preNode = newHead
            while postNode is not None and postNode.val < head.val:
                preNode = preNode.next
                postNode = postNode.next

            tmpNode = head.next
            preNode.next = head
            head.next = postNode
            head = tmpNode
        return newHead.next

    # Fast,100+ms
    def insertionSortList(self, head):
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        pre = dummy
        dummy.next = head
        curr = head
        while curr and curr.next:
            val = curr.next.val
            if curr.val < val:
                curr = curr.next
                continue
            if pre.next.val > val:
                pre = dummy
            while pre.next.val < val:
                pre = pre.next
            new = curr.next
            curr.next = new.next
            new.next = pre.next
            pre.next = new

        return dummy.next

fast里面如果发现原来的链表中已经部分有序排列，那么不会对这个部分作移动。
但是你的slow里面，对于原链表中的每一个值，你都要在新的链表找到对应的插入位置并且把这个ListNode放进去。