Java solution: 3ms quick sort (99.5%), 7ms merge sort (74%)


  • 2
    S
    //quick sort
    public ListNode sortList(ListNode head) {
                if (head == null || head.next == null)
                    return head;
                ListNode pivot = head;
                ListNode left = new ListNode(-1);
                ListNode right = new ListNode(-1);
                ListNode leftHead = left;
                ListNode rightHead = right;
                ListNode pivotHead = pivot;
                ListNode crt = head.next;
                if (crt == null)
                    return pivot;
                    
                while(crt != null) {
                    if (crt.val < pivot.val) {
                        left.next = crt;
                        left = left.next;
                    } else if (crt.val > pivot.val){
                        right.next = crt;
                        right = right.next;
                    } else {
                        pivot.next = crt;
                        pivot = pivot.next;
                    }
                    crt = crt.next;
                }
                
                pivot.next = null;
                left.next = null;
                right.next = null;
                left = sortList(leftHead.next);
                right = sortList(rightHead.next);
                pivot.next = right;
                ListNode re = left;
                
                while (left != null && left.next != null) {
                    left = left.next;
                }
                
                if (left == null) 
                    re = pivotHead;
                else 
                    left.next = pivotHead;
                return re;
            }
    

    //merge sort

    public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) 
                return head;
                
            ListNode prev = head;
            ListNode slow = head;
            ListNode fast = head;
            while (fast != null && fast.next != null) {
                prev = slow;
                slow = slow.next;
                fast = fast.next.next;
            }
            
            prev.next = null;
            ListNode firstHalf = sortList(head);
            ListNode secondHalf = sortList(slow);
            return merge(firstHalf, secondHalf);
        }
        
        private ListNode merge(ListNode firstHalf, ListNode secondHalf) {
            ListNode dummy = new ListNode(-1);
            ListNode crt = dummy;
            while(firstHalf != null && secondHalf != null) {
                if (firstHalf.val < secondHalf.val) {
                    crt.next = firstHalf;
                    firstHalf = firstHalf.next;
                } else {
                    crt.next = secondHalf;
                    secondHalf = secondHalf.next;
                }
                    
                crt = crt.next;
            }
            
            if (firstHalf != null)
                crt.next = firstHalf;
            else
                crt.next = secondHalf;
            
            return dummy.next;
        }

  • 0
    H

    recursion is not correct


  • 0
    S

    both are accepted solutions


  • 0
    W

    recursion requires at least lgN stack space.
    It is not constant space. OJ may not be so effective in checking the space usage.


  • 0
    S

    i didnt say its constant space.


  • 0
    S

    for quick sort, its constant space.


  • 0
    W

    The problem explicitly says "Sort a linked list in O(n log n) time using constant space complexity."

    Why is the quicksort constant space? It has recursion as well. Don't you get a few levels (lgN) of stack?


  • 0
    S

    you are right, i didnt notice that it requires constant space. do you have any idea to revise them to constant space?


  • 0
    W

    The only way I can think of, is the bottom-up mergesort.
    It is iterative, so constant space can be achieved.


  • 0
    S

    thank you for sharing the idea.


Log in to reply
 

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