LeetCode 148 [Sort List]

原题

在 O(n log n) 时间复杂度和常数级的空间复杂度下给链表排序。

样例给出 1->3->2->null，给它排序变成 1->2->3->null.

解题思路

• 方法一：遍历链表，存入数组中，排序数组，然后重新构建链表
• 方法二：直接操作链表，Merge Sort，先局部有序再整体有序，找中点，然后左半部分和右半部分分别递归merge sort (Divide and Conquer)
• 总结：
• 对于数组，quick sort好于merge sort，因为quick sort是in-place，而merge sort需要额外空间，开辟空间/回收空间都要耗费时间
• 对于链表，merge sort并不需要额外空间

完整代码

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

# 方法一
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        ans = []
        tmp = head
        while tmp != None:
            ans.append(tmp.val)
            tmp = tmp.next

        ans.sort()
        tmp = head
        for i in ans:
            tmp.val = i
            tmp = tmp.next
        return head

# 方法二
class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head == None or head.next == None:
            return head

        mid = self.findMiddle(head)

        right = self.sortList(mid.next)
        mid.next = None
        left = self.sortList(head)

        return self.merge(left, right)
        
    def findMiddle(self, head):
        slow, fast = head, head.next
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
        return slow    

    def merge(self, head1, head2):
        dummy = ListNode(0)
        head = dummy
        while head1 and head2:
            if head1.val < head2.val:
                head.next = head1
                head1 = head1.next
            else:
                head.next = head2
                head2 = head2.next
            head = head.next
        if head1:
            head.next = head1
        if head2:
            head.next = head2
        return dummy.next