Skip to content

147 insertion sort list

147. Insertion Sort List

题目: https://leetcode.com/problems/insertion-sort-list/

难度: Medium

insertion sort 也是入门必备,一个元素本身被认为是sort的,一个简单的理解是打牌,然后进入第二个元素的时候,看它是比第一个元素大还是小,做排序,进入下一个元素的时候再看再移。

伪码

for i ← 1 to length(A)-1
    j ← i
    while j > 0 and A[j-1] > A[j]
        swap A[j] and A[j-1]
        j ← j - 1
    end while
end for

这个伪码对于list可能适用性没有那么强,则考虑,从第二个node开始,那么从开始开始看,找到这个node应该插入的位置,插入。

就是这样,就是会超时||||

class Solution(object):
    def insertionSortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head

        dummy = ListNode(-1)
        dummy.next = head

        prev = head 
        cur = head.next

        while cur:
            p = dummy
            while p.next.val <= cur.val and p != prev:
                p = p.next
            if p != prev:
                prev.next = cur.next
                cur.next = p.next
                p.next = cur
            prev = cur
            cur = cur.next

        return dummy.next


回到顶部