leetcode 148

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

148

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

1
2
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2
Input: -1->5->3->4->0
Output: -1->0->3->4->5

思路: O(nlogn)采用归并排序

总结,归并排序的本质是两个有序数组排序

{cmd
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

class ListNode:
    def __init__(self, val):
        self.val, self.next = val, None


class LinkList:
    def __init__(self):
        self.head = None

    def init_list(self, data):
        assert type(data) == list
        if data:
            point = self.head = ListNode(data[0])
            for i in data[1:]:
                point.next = ListNode(i)
                point = point.next
        return self.head

    @staticmethod
    def print_list(head):
        data = []
        while head:
            data.append(str(head.val))
            head = head.next
        print("->".join(data))

class Solution(object):
    def merge(self, h1, h2):
        dummy = tail = ListNode(None)
        while h1 and h2:
            if h1.val < h2.val:
                tail.next, tail, h1 = h1, h1, h1.next
            else:
                tail.next, tail, h2 = h2, h2, h2.next

        tail.next = h1 or h2
        return dummy.next

    def sortList(self, head):
        if not head or not head.next:
            return head

        pre, slow, fast = None, head, head
        while fast and fast.next:
            pre, slow, fast = slow, slow.next, fast.next.next
        pre.next = None

        return self.merge(*map(self.sortList, (head, slow)))



if __name__ == '__main__':
    data = [4, 6, 1, 3, 4, 2]
    link_list = LinkList()
    link_list.init_list(data)
    print("example:")
    link_list.print_list(link_list.head)
    print("result:")
    result = Solution().sortList(link_list.head)
    link_list.print_list(result)

知识点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def sortList(self, head):
    if not head or not head.next:
        return head

    pre, slow, fast = None, head, head
    while fast and fast.next:
        pre, slow, fast = slow, slow.next, fast.next.next
    pre.next = None

    return self.merge(*map(self.sortList, (head, slow))

等价于:
def sortList(self, head):
    if not head or not head.next:
        return head

    pre, slow, fast = None, head, head
    while fast and fast.next:
        pre, slow, fast = slow, slow.next, fast.next.next
    pre.next = None

    left = self.sortList(head)
    right = self.sortList(slow)
    return self.merge(left, right)
  1. map函数的原型是map(function, iterable, …)，它的返回结果是一个列表,函数式编程
{cmd
1
2
3
4
def mul(x):
    return x*x
res=map(mul,(1,2))
print(res)
  1. (*)号操作符
{cmd
1
2
3
4
def add(a,b):
    print(a+b)
l= [1,2]
add(*l)
  1. 排序时间复杂度
排序方法 平均时间 最好时间 最坏时间
桶排序(不稳定) O(n) O(n) O(n)
基数排序(稳定) O(n) O(n) O(n)
归并排序(稳定) O(nlogn) O(nlogn) O(nlogn)
快速排序(不稳定) O(nlogn) O(nlogn) O(n^2)
堆排序(不稳定) O(nlogn) O(nlogn) O(nlogn)
希尔排序(不稳定) O(n^1.25)
冒泡排序(稳定) O(n^2) O(n) O(n^2)
选择排序(不稳定) O(n^2) O(n^2) O(n^2)
直接插入排序(稳定) O(n^2) O(n) O(n^2)
  1. 归并排序
    思路:分解->两个子序列排序
    4.1. 如何分解,及如何递归的解决这个问题
    4.2. 两个子序列排序