Java solution using recursive quicksort algorithm


  • -1
    L
    public class Solution {
        public ListNode sortList(ListNode head) {
            if(head==null)
                return null;
            
            int sum = 0, count = 0, value = head.val;
            boolean same = true;
            double pivot = 0.0;
            ListNode lessHead=null, lessTail=null, geqHead=null, geqTail=null, currentNode=head;
            while(currentNode != null){
                if(currentNode.val!=value)
                    same = false;
                sum += currentNode.val;
                currentNode = currentNode.next;
                count++;
            }
            
            if(same) // all values are the same
                return head;
                
            pivot = 1.0*sum/count;
                    
            currentNode = head;
            if(head.next != null){
                while(currentNode!=null){
                    if(currentNode.val<pivot){ // go into less
                        if(lessTail!=null){
                            lessTail.next = currentNode;
                            lessTail = lessTail.next;
                          
                        }else{
                            lessHead = new ListNode(currentNode.val);
                            lessTail = lessHead;
                        }
                    }else{
                        if(geqTail!=null){
                            geqTail.next = currentNode;
                            geqTail = geqTail.next;
                        }else{
                            geqHead = new ListNode(currentNode.val);
                            geqTail = geqHead;
                        }
                    }
                    currentNode = currentNode.next;
                }
               
                if(lessTail!=null)
                   lessTail.next = null;
                if(geqTail!=null)
                   geqTail.next = null;
                
                lessHead = sortList(lessHead);
                if(lessHead != null){
                    lessTail = lessHead;
                    while(lessTail.next!=null){
                        lessTail = lessTail.next;
                    }
                    lessTail.next = sortList(geqHead);
                }else
                    lessHead = sortList(geqHead);
            }else{
                return head;
            }
            return lessHead;
        }
    }

Log in to reply
 

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