MergeSort with strict O(1) space. Please comment if you have improvement suggestion.


  • 0
    O
    public ListNode sortList(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        int n = 0, lCnter, rCnter;
        while (head != null) { head = head.next; n++;}
        ListNode cur, tail = null; //cur is always previous node of head of each sub-merged list
        ListNode l, r;
        for (int mergeN = 2; mergeN / 2 <= n; mergeN *= 2) {
            cur = dummyHead;
            for (int subN = 0; subN < n; subN += mergeN) {
                l = cur.next; r = l;
                for (int k = 0; k < mergeN / 2; k++) {
                        r = r.next;
                        if (r == null) break;   
                }
                if (r == null) break; //other half of is empty, no need to sort
                
                //merge l list and r list with mergeN elements
                lCnter = 0; rCnter = 0;
                if (l.val < r.val) {
                    cur.next = l;
                    l = l.next;
                    lCnter++;
                } else {
                    cur.next = r;
                    r = r.next;
                    rCnter++;
                }
                
                for (int k = 1; true; k++) {
                    cur = cur.next;
                    if (lCnter == mergeN / 2 && (rCnter == mergeN / 2 || r == null)) break;
                    if (lCnter == mergeN / 2) {
                        cur.next = r;
                        tail = r;
                        r = r.next;
                        rCnter++;
                        continue;
                    }
                    if (rCnter == mergeN / 2 || r == null) {
                        cur.next = l;
                        tail = l;
                        l = l.next;
                        lCnter++;
                        continue;
                    }
                    if (l.val < r.val) {
                        cur.next = l;
                        l = l.next;
                        lCnter++;
                    } else {
                        cur.next = r;
                        r = r.next;
                        rCnter++;
                    }
                }
                cur.next = r;
            }
        }
        return dummyHead.next;
    }

Log in to reply
 

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