【LeetCode with Python】 147. Insertion Sort List

题目

原题页面:https://leetcode.com/problems/insertion-sort-list/
本文地址:http://leetcode.xnerv.wang/insertion-sort-list/
题目类型:Linked List, Sort
难度评价:Medium
类似题目:(M) Sort List

Sort a linked list using insertion sort.


分析

链表的插入排序。先是看到网上有人用C++写的解法,生成一个新的链表,每次都将下一个结点插入到这个新链表中,于是用Python仿写之,然超时。后来改成不再生成新链表,而是直接在原链表上原地排序,并且加入了一个判断条件,避免当需要排序的链表已经有序时再做过多无用功(因为前一次超时的原因就是判题系统给了一个超长的已有序链表-_-)。


代码

class Solution:

    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        if None == head or None == head.next:
            return head

        new_head = ListNode(0)
        new_head.next = head

        last = new_head.next
        cur = new_head.next.next
        while None != cur:
            if cur.val >= last.val:
                last = cur
                cur = cur.next
                continue
            ins = new_head
            while None != ins.next and ins.next.val <= cur.val: # stable sort
                ins = ins.next
            last.next, cur.next, ins.next, cur = cur.next, ins.next, cur, cur.next

        return new_head.next

results matching ""

    No results matching ""