Java quicksort 4ms


  • 6
    U
    public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        
        ListNode pivot = head;
        head = head.next;
        pivot.next = null;
        if (head == null) return pivot;
        ListNode small = new ListNode(0);
        ListNode large = new ListNode(0);
        ListNode p = pivot;
        ListNode s = small;
        ListNode l = large;
        while (head!=null) {
            if (head.val < pivot.val) {
                s.next = head;
                s = s.next;
            } else if (head.val == pivot.val) {
                p.next = head;
                p = p.next;
            } else {
                l.next = head;
                l = l.next;
            }
            head = head.next;
        }
        l.next = null;
        s.next = null;
        p.next = null;
        ListNode ss = sortList(small.next);
        if (ss == null) {
            ss = pivot;    
        } else {
            ListNode sss = ss;
            while (sss.next!=null) {
                sss = sss.next;
            }
            sss.next = pivot;
        }
        p.next = sortList(large.next);
        return ss;
    }
    

    }


  • 0
    O
    public ListNode sortList(ListNode head) {
            ListNode p1=head;
            ListNode l1=new ListNode(-1);
            int N=0;
            while(p1!=null){
            	p1=p1.next;
            	N++;
            }
            ListNode[] p=new ListNode[N];
            int i=0;
            while(head!=null){
                p[i]=head;
                head=head.next;
                i++;
            }
            Arrays.sort(p,new ListNodeCompare());
            ListNode p2=l1;
            int j=0;
            while(j<N){
            	l1.next=p[j];
            	l1=l1.next;
            	j++;
            }
            return p2.next;
        }
    	@SuppressWarnings("hiding")
    	public static class ListNodeCompare implements Comparator<ListNode>{
    		@Override
    		public int compare(ListNode l1, ListNode l2) {
    			// TODO Auto-generated method stub
    			
    			return l1.val-l2.val;
    		}
    	}

Log in to reply
 

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