148.⭐排序链表

https://leetcode-cn.com/problems/sort-list/

• 笔试的时候直接申请一个数组，然后把链表中每个节点都加到数组里去，然后排序数组，最后再重新把链表串起来

进阶：

• 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

两个链表在merge的时候不涉及数组的覆盖问题，所以是可以做到空间复杂度O(1)

/**
     * 法二：自底向上的归并排序  时间复杂度O(nlogn), 空间复杂度O(1)
     */
    public ListNode sortList2(ListNode head) {
        if (head == null) {
            return head;
        }
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            cur = cur.next;
            length++;
        }
        ListNode dummy = new ListNode(0, head);
        //步长
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode prev = dummy;
            cur = dummy.next;
            while (cur != null) {
                ListNode head1 = cur;
                for (int i = 1; i < subLength && cur.next != null ; i++){
                    cur = cur.next;
                }
                ListNode head2 = cur.next;
                cur.next = null;
                cur = head2;
                for (int i = 1; i < subLength && cur != null && cur.next != null; i++) {
                    cur = cur.next;
                }
                ListNode next = null;
                if (cur != null) {
                    next = cur.next;
                    cur.next = null;
                }
                ListNode merged = merge(head1, head2);
                prev.next = merged;
                while (prev.next != null) {
                    prev = prev.next;
                }
                cur = next;
            }
        }
        return dummy.next;
    }
    private ListNode merge(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while (node1 != null && node2 != null) {
            if (node1.val <= node2.val) {
                cur.next = node1;
                node1 = node1.next;
            } else {
                cur.next = node2;
                node2 = node2.next;
            }
            cur = cur.next;
        }
        if (node1 != null) {
            cur.next = node1;
        }
        if (node2 != null) {
            cur.next = node2;
        }
        return dummy.next;
    }