[Leetcode] Sort List

Sort a linked list in O(n log n) time using constant space complexity.
比较难的链表题，用归并排序可以满足时间复杂度O(nlogn)，使用递归的实现如下。

public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        
        int cnt = 0;
        ListNode temp = head;
        while(temp != null) {
            temp = temp.next; cnt++;
        }
        int hal = cnt / 2; // partition
        temp = head;
        while(hal > 1 && temp.next != null) {
            temp = temp.next; hal--;
        }
        ListNode head2 = temp.next;
        temp.next = null;
        head = sortList(head); // recursion
        head2 = sortList(head2);
        ListNode dummy = new ListNode(0);
        temp = dummy; // merge the two parts
        while(head != null && head2 != null) {
            if(head.val < head2.val) {
                temp.next = head;
                temp = temp.next;
                head = head.next;
            }
            else {
                temp.next = head2;
                temp = temp.next;
                head2 = head2.next;
            }
        }
        if(head != null) {
            temp.next = head;
        }
        else {
            temp.next = head2;
        }
        
        return dummy.next;
    }

但是使用递归的方法实现需要用到O(logn)的栈空间，为了满足空间复杂度，需要使用bottom up的归并排序的实现，代码相对复杂很多，主要涉及链表的partition和merge。

public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode temp = head;
        int l = 0;
        ListNode dummy = new ListNode(0); dummy.next = head;
        ListNode tdummy = new ListNode(0);
        while(temp != null) {
            temp = temp.next; l++;
        }
        int len = 1;
        while(l > len) {
            ListNode prior = dummy;
            while(prior.next != null) {
                ListNode head1 = prior.next;
                prior.next = null;
                ListNode temp1 = head1; // find the first part
                int cnt = len;
                while(cnt > 1 && temp1.next != null) {
                    temp1 = temp1.next; cnt--;
                }
                if(cnt != 1) {
                    prior.next = head1;
                    break;
                }
                ListNode head2 = temp1.next;
                temp1.next = null; // first part's end
                if(head2 == null) {
                    prior.next = head1;
                    break;
                }
                ListNode temp2 = head2; // find the second part
                cnt = len;
                while(cnt > 1 && temp2.next != null) {
                    temp2 = temp2.next; cnt--;
                }
                ListNode tail = temp2.next;
                temp2.next = null; // second part's end
                tdummy.next = null;
                temp = tdummy; // merge two parts
                while(head1 != null && head2 != null) {
                    if(head1.val < head2.val) {
                        temp.next = head1;
                        temp = temp.next;
                        head1 = head1.next;
                    }
                    else {
                        temp.next = head2;
                        temp = temp.next;
                        head2 = head2.next;
                    }
                }
                if(head1 != null) {
                    temp.next = head1;
                }
                else {
                    temp.next = head2;
                }
                prior.next = tdummy.next; // relink
                while(prior.next != null) prior = prior.next;
                prior.next = tail;
            }
            len = len * 2;
        }
        
        return dummy.next;
    }