0(nlogn)solution,O(1)space,but a little long


  • 1
    S
    public ListNode sortList(ListNode head) {
        int length=0,stepLen=1;
        ListNode cur=head,first,second,quard=new ListNode(0),pre;
        quard.next=head;
        first=quard;
        while (cur!=null){
            length++;
            cur=cur.next;
        }
        while (stepLen<length) {
            first=quard;
            cur=first.next;
            while (cur != null) {
                pre=first;
                cur=pre.next;
                first=cur;
                if(cur==null)
                    break;
                for (int i = 0; i < stepLen&&cur!=null; i++)
                    cur = cur.next;
                second = cur;
                first=merge(first,second,stepLen,pre);
            }
            stepLen *= 2;
        }
        return quard.next;
    }
    private ListNode merge(ListNode first,ListNode second,int lenght,ListNode pre){
        if(second==null)
            return first;
        int i=0,j=0;
        ListNode tail=null;
        while (i<lenght&&j<lenght&&second!=null)
        if(first.val>second.val){
            pre.next=second;
            pre=second;
            second=second.next;
            j++;
            if(j==lenght){
                tail=second;
            }
        }
        else {
            pre.next=first;
            pre=first;
            first=first.next;
            i++;
        }
        while (i<lenght){
            pre.next=first;
            pre=first;
            first=first.next;
            i++;
    
    
        }
        while (second!=null&&j<lenght){
            pre.next=second;
            pre=second;
            second=second.next;
            j++;
            if(j==lenght)
                tail=second;
        }
        pre.next=tail;
        return pre;
    }

Log in to reply
 

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