Java merge sort,non recursion


  • 0
    C
    public class Solution {
        ListNode mHead = null;
        public ListNode sortList(ListNode head) {
            if(head == null || head.next == null){
                return head;
            }
            mHead = head;
            int k=1;
            while(true){
    
                ListNode start = mHead;
                ListNode preStart = null;
                ListNode slowPre = null;
    
                while(start != null){
                    ListNode slow = start;
    
                    ListNode fastPre = null;
                    ListNode fast = start;
                    ListNode fastEnd = fast;
    
                    int j = 0;
                    while(j++ < k && fast != null){
                        fastPre = fast;
                        fast = fast.next;
                        if(fastEnd != null && fastEnd.next != null) {
                            fastEnd = fastEnd.next.next;
    
                        }else{
                            fastEnd = null;
                        }
                    }
                    slowPre = sortTwo(slowPre,slow,fastPre,fast,fastEnd);
                    preStart = start;
                    start = fastEnd;
    
                }
                if(preStart == null || preStart == mHead){
                    break;
                }
                k*=2;
            }
            return mHead;
        }
    
        private ListNode sortTwo(ListNode slowPre,ListNode slow,ListNode fastPre,ListNode fast,ListNode fastEnd){
            ListNode slowEnd = fastPre;
            if(slow == null || fast == null) return null;
            boolean isHead = false;
            if(slowPre == null) isHead = true;
    
            while(true){
                if(slow.val > fast.val) {
    
                    fastPre.next = fast.next;
                    if(isHead && slowPre == null){
                        fast.next = slow;
                        mHead = fast;
                    }else {
                        slowPre.next = fast;
                        fast.next = slow;
                    }
                    slowPre = fast;
    
                    fast = fastPre.next;
                    if (fast == fastEnd || fast == null) {
                        break;
                    }
                }else{
                    if(slow == slowEnd) break;
                    slowPre = slow;
                    slow = slow.next;
                }
            }
    
            while(fast != fastEnd && fast != null){
                fastPre = fast;
                fast = fast.next;
            }
            return fastPre;
        }
    
    }
    

Log in to reply
 

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