Iterative merge method. Could someone help me improve it? it is a little bit slow. 12m


  • 0
    Z
    public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) return head;
            
            int size = 0;
            ListNode fakehead = new ListNode(-1);
            fakehead.next = head;
            
            for (ListNode len = head; len!= null; len = len.next)
                size ++;
            
            for (int length = 1; length < size; length *= 2)
            {
                ListNode firstBegin = fakehead.next;
                ListNode secondBegin = fakehead.next;
                ListNode temp = fakehead;
                
                for (int begin = 0 ; begin < size; begin += 2 * length)
                {
                    int valid = size - begin;
                    int leftcounter = Math.min(length, valid);
                    int rightcounter = Math.min(length, valid - leftcounter);
                    
                    for (int i = 0; i < leftcounter; i++)
                        secondBegin = secondBegin.next;
                    
                    while (leftcounter > 0 && rightcounter > 0)
                    {
                        if (firstBegin.val > secondBegin.val)
                        {
                            temp.next = secondBegin;
                            secondBegin = secondBegin.next;
                            rightcounter--;
                        }
                        else
                        {
                            temp.next = firstBegin;
                            firstBegin = firstBegin.next;
                            leftcounter--;
                        }
                        temp = temp.next;
                    }
                    
                    while (leftcounter > 0)
                    {
                        temp.next = firstBegin;
                        firstBegin = firstBegin.next;
                        leftcounter--;
                        temp = temp.next;
                    }
                    
                    while (rightcounter > 0)
                    {
                        temp.next = secondBegin;
                        secondBegin = secondBegin.next;
                        rightcounter--;
                        temp = temp.next;
                    }
                    
                    temp.next = firstBegin = secondBegin;
                }
            }
            return fakehead.next;
        }

Log in to reply
 

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