My qsort solution, Python


  • 1
    S
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param head, a ListNode
        # @return a ListNode
        def sortList(self, head):
            if head is None or head.next is None:
                return head
            mid = (head.val + head.next.val) / 2
            if head.val > head.next.val:
                lhead, rhead = head.next, head
            else:
                lhead, rhead = head, head.next
            lit, rit = lhead, rhead
            it = head.next.next
            lcount, rcount = 0, 0
            while it is not None:
                if it.val > mid:
                    rit.next = it
                    rit = it
                    rcount += 1
                elif it.val < mid:
                    lit.next = it
                    lit = it
                    lcount += 1
                else:
                    if lcount < rcount:
                        lit.next = it
                        lit = it
                        lcount += 1
                    else:
                        rit.next = it
                        rit = it
                        rcount += 1
                it = it.next
            lit.next, rit.next = None, None
            lhead = self.sortList(lhead)
            rhead = self.sortList(rhead)
            it = lhead
            while it.next is not None:
                it = it.next
            it.next = rhead
            return lhead

  • 0
    L

    Nice trick with the count to balance the partition. I was wonder if it works without this balancing.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.