Merge-sort with detailed explanation. Java, O(1) space, O(nlogn) time


  • 1
    C

    Just like merge-sort in an array, what we should do is to merge-sort the list.
    Take [3->1->2->5->6->4->3]->null for example.
    We just find the middle point (5), and cut it to two lists [3->1->2->5]->6 and [6->4->3]->null.
    Here 6 in the first list meas the next ListNode. Then we need to merge [3->1->2->5] with next 6.

    In order to merge sort, we just need to compare the two sublists. Each time, choose the smaller one in the list. Remember, do not use any extra memory during merge!

    Here is a sample.

    (1) [3->1->2->5->6->4->3]->null
    (2) [3->1->2->5]->6, [6->4->3]->null // split (1)               
    (3) [3->1]->2, [2->5]->6 // split (2.1)
    (4) [3]->1, [1]->2 // split (3.1)
    (5) [1->3]->2 // merge (4)
    (6) [2]->5, [5]->6 // split (3.2)
    (7) [2->5]->6 // merge (5)
    (8) [1->2->3->5]->6 // merge (5) and (7)
    (9) [6->4]->3, [3]->null // split (2.2)
    (10) [6]->4, [4]->3 // split (9.1)
    (11) [4->6]->3 // merge (10)
    (12) [3->4->6]->null // merge (10) and (9.2)
    (13) [1->2->3->3->4->5->6]->null // merge (8) and (12)
    

    So, we can remember after in order to reform the list.

    Here is the code with comments.

    public class Solution {
        public ListNode sortList(ListNode head) {
            if (head==null || head.next==null) return head;
            ListNode end=head;
            while (end.next!=null) end=end.next; // find the end point
            return sortList(head, end, null);
        }
        // sort from head to end. 'after' is the next point of this sub-list.
        private ListNode sortList(ListNode head, ListNode end, ListNode after) { 
            if (head==end) {return head;}
            ListNode p=findMiddlePoint(head, after);
            head=sortList(head, p, p.next);
            p=findMiddlePoint(head, after);
            p.next=sortList(p.next, end, after);
            return merge(head, p.next, after);
        }
        // find the middle point in order to split the list
        private ListNode findMiddlePoint(ListNode head, ListNode after) {
            ListNode p=head, q=head;
            while (q.next!=after && q.next.next!=after) {
                p=p.next;
                q=q.next.next;
            }
            return p;
        }
        // merge the two array. Remember: the after of l1 is l2.
        private ListNode merge(ListNode l1, ListNode l2, ListNode after) {
            ListNode p=l1, q=l2;
            ListNode w=null, head=null;
            while (p!=l2 || q!=after) {
                if (p==l2) {
                    if (w==null) {
                        w=q;
                        head=w;
                    }
                    else {
                        w.next=q;
                        w=w.next;
                    }
                    q=q.next;
                    continue;
                }
                if (q==after) {
                    if (w==null) {
                        w=p;
                        head=w;
                    }
                    else {
                        w.next=p;
                        w=w.next;
                    }
                    p=p.next;
                    continue;
                }
                if (p.val<q.val) {
                    if (w==null) {
                        w=p;
                        head=w;
                    }
                    else {
                        w.next=p;
                        w=w.next;
                    }
                    p=p.next;
                }
                else {
                    if (w==null) {
                        w=q;
                        head=w;
                    }
                    else {
                        w.next=q;
                        w=w.next;
                    }
                    q=q.next;
                }
            }
            w.next=after;
            return head;
        }
    }
    

Log in to reply
 

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