This is quicksort based solution. beat 95%.


  • 0
    T
        public ListNode sortList(ListNode head) {
            if (head==null || head.next==null)
                return head;
    
            ListNode pivot = head, pivotTail = pivot;
    
            ListNode leftHead=new ListNode(0), rightHead=new ListNode(0);
            ListNode leftTail = leftHead, rightTail = rightHead;
            ListNode tmp = head.next;
            while (tmp != null) {
                if (tmp.val < pivot.val )
                    leftTail = (leftTail.next = tmp);
                else if (tmp.val > pivot.val )
                    rightTail = (rightTail.next=tmp);
                else
                    pivotTail = (pivotTail.next=tmp);
                tmp = tmp.next;
            }
            leftTail.next = null;
            rightTail.next = null;
    
            leftHead.next = sortList(leftHead.next);
            rightHead.next = sortList(rightHead.next);
    
            tmp = leftHead;
            while (tmp.next!=null)
                tmp = tmp.next;
            tmp.next = pivot;
            pivotTail.next = rightHead.next;
    
            return leftHead.next;
            
        }
    

  • 0
    A

    @taowu99 I don't think recursive is "constant space" as the problem stipulates.


Log in to reply
 

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