java use quick sort to sort the list, beats 93.21%


  • 1
    K

    like the method of three pointers. Maybe not very short,but the thought is quite clear and easily understood.

    public class Solution {
        public ListNode sortList(ListNode head) {
            if(head==null || head.next==null){
                return  head;
            }
            ListNode mid = getMid(head);
            int midval= mid.val;
            ListNode leftdummy=new ListNode(0),middummy=new ListNode(0),rightdummy=new ListNode(0);
            ListNode leftwork=leftdummy,midwork=middummy,rightwork=rightdummy;
            ListNode work=head;
            while(work!=null){
                if(work.val<midval){
                    leftwork.next=work;
                    leftwork=work;
                }
                else if(work.val==midval){
                    midwork.next=work;
                    midwork=work;
                }
                else{
                    rightwork.next=work;
                    rightwork=work;
                }
                work=work.next;
            }
            leftwork.next=null;  midwork.next=null;  rightwork.next=null;
            ListNode left= sortList(leftdummy.next);
            ListNode right = sortList (rightdummy.next);
            return connectAll(left,middummy.next,right);
            
        }
        public ListNode connectAll(ListNode l1,ListNode l2,ListNode l3){
            ListNode dummy= new ListNode (0);
            ListNode work=dummy;
            if(l1!=null){
                work.next=l1;
                work=tail(l1);
            }
            if(l2!=null){
                work.next=l2;
                work=tail(l2);
            }
            if(l3!=null){
                work.next=l3;
            }
            return dummy.next;
        }
        
        public ListNode tail (ListNode l){
            ListNode work=l;
            while(work.next!=null){
                work=work.next;
            }
            return work;
        }
        
        public ListNode getMid(ListNode head){
            ListNode slow = head,fast=head;
            while(fast!=null && fast.next!=null){
                slow=slow.next;
                fast=fast.next.next;
            }
            return slow;
        }
    }
    

  • 0
    A

    @KnightRider Recursive, not really constant space.


Log in to reply
 

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