My Java O(1) Space O(logn) Time Answer


  • 0
    T

    Share My answer here. At the beginning, a group of 1 node are sorted within its group (there is only one item in group), merge these groups two by two which results in groups of two sorted items. Merge these groups into groups of 4 and so on - keep doubling group size every time and until the group size is larger than the whole list.

    public class Solution {
        public ListNode sortList(ListNode head) {
            int listSize = 0;
            int groupSize = 1;
            ListNode h0 = new ListNode(0);
            h0.next = head;
            ListNode tail;
            ListNode p0 = new ListNode(0);
            ListNode p1, p2, p3;
            p1 = head;
            while (p1 != null) {
                p1 = p1.next;
                listSize++;
            }
            if (head == null) {
                return null;
            }
            while (groupSize <= listSize) {
                p3 = h0.next;
                tail = h0;
                while (p3 != null) {
                    p0.next = p3;
                    p1 = p0;
                    p2 = p0;
                    for (int i = 0; i < groupSize ; i++) {
                        p1 = p1.next;
                        if (p2.next != null) {
                            p2 = p2.next;
                        }
                        if (p2.next != null) {
                            p2 = p2.next;
                        }
                    }
                    p3 = p2.next;
                    p2.next = null;
                    p2 = p1.next;
                    p1.next = null;
                    p1 = p0.next;
                    
                    while (p1 != null || p2 != null) {
                        if (p1 == null) {
                            tail.next = p2;
                            p2 = p2.next;
                            tail = tail.next;
                        } else if (p2 == null) {
                            tail.next = p1;
                            p1 = p1.next;
                            tail = tail.next;
                        } else if (p1.val <= p2.val) {
                            tail.next = p1;
                            p1 = p1.next;
                            tail = tail.next;
                        } else {
                            tail.next = p2;
                            p2 = p2.next;
                            tail = tail.next;
                        }
                    }
                }
                groupSize *= 2;
            }
            return h0.next;
        }
    }
    

Log in to reply
 

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