Leetcode解题-Insertion Sort List

发表于   |   分类于   |  

描述

Sort a linked list using insertion sort.

分析

链表的插入排序，不难，但程序写对不容易。

代码

总是超时的解，发誓逻辑是对的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(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

针对已排序情况做优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(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

热评文章