Sort List

Question

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

Thoughts

要满足O(nlogn)的sorting algorithm有quicksort, mergesort, heapsort 这里我们用mergesort, 不断recursively split into half, 再merge 因为是linkedlist, 没有像array一样的slice function, 所以额外自己写了一个splitList的function来分割

Solution

class Solution:
    """
    @param head: The first node of the linked list.
    @return: You should return the head of the sorted linked list,
                  using constant space complexity.
    """
    def sortList(self, head):
        # write your code here
        length = self.length(head)
        if length > 1:
            mid = length / 2
            leftList, rightList = self.splitList(head, mid)
            leftList = self.sortList(leftList)
            rightList = self.sortList(rightList)
            head = self.merge(leftList, rightList)
        return head

    def splitList(self, head, number):
        pre = head
        i = 1
        while i < number:
            i += 1
            pre = pre.next
        rightHead = pre.next
        pre.next = None
        return head, rightHead

    def length(self, head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

    def merge(self, leftList, rightList):
        dummy = ListNode(0)
        lastNode = dummy
        while leftList and rightList:
            if leftList.val < rightList.val:
                lastNode.next = leftList
                leftList = leftList.next
            else:
                lastNode.next = rightList
                rightList = rightList.next
            lastNode = lastNode.next
        if leftList:
            lastNode.next = leftList
        if rightList:
            lastNode.next = rightList
        return dummy.next

    """
    def printList(self, head):                                                                                                            
        string = "list: " + str(head.val)
        while head.next:
            head = head.next
            string += "->" + str(head.val)
        print string
    """