非递归方式进行归并排序链表

题目来源：LeetCode 148

题目大意

给你一个链表， 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

啥？把链表排序，把时间复杂度控制在O(nlogn)？，链表不像数组，排序没有那么方便啊！归并排序，常数级空间复杂度？那只能非递归实现了~~

不过我不知道该怎么写，看了评论区，自己整理了一下。

算法实现

ListNode mergetSort(ListNode head) {
    if (head == null || head.next == null) return head;
    int listLength = 0;
    for (ListNode l = head; l != null; l = l.next) listLength++;
    ListNode helperRoot = new ListNode(0);
    helperRoot.next = head;
    ListNode helper = helperRoot;
    // 步长， 即每个子区间的长度
    int step = 1;
    while (step < listLength) {
        helper = helperRoot;
        for (ListNode start = helperRoot.next; start != null; ) {
            ListNode end = start, mid = start, pre = start;
            int len = 0;
            while (len < step && mid != null) {
                len++;
                pre = mid;
                mid = mid.next;
            }
            pre.next = null;
            end = mid;
            pre = mid;
            len = 0;
            while (len < step && end != null) {
                len++;
                pre = end;
                end = end.next;
            }
            if (pre != null) pre.next = null;
            ListNode nextStart = end;
            ListNode[] merger = merger(start, mid);
            helper.next = merger[0];
            merger[1].next = nextStart;
            start = nextStart;
            helper = merger[1];
        }
        step *= 2;
    }
    return helperRoot.next;
}

// 返回合并后的链表头指针和尾指针
ListNode[] merger(ListNode left, ListNode rightStart) {
    ListNode leftStart = left;
    ListNode listTail = left;
    if (leftStart == null && rightStart == null) return null;
    // 其实在本题中， 左边链表不会是null
    if (leftStart == null) {
        listTail = rightStart;
        while (listTail.next != null) listTail = listTail.next;
        return new ListNode[]{rightStart, listTail};
    }
    if (rightStart == null) {
        while (listTail.next != null) listTail = listTail.next;
        return new ListNode[]{left, listTail};
    }
    ListNode root = new ListNode(0);
    ListNode tail = root;
    while (rightStart != null && leftStart != null) {
        if (leftStart.val < rightStart.val) {
            tail.next = leftStart;
            tail = tail.next;
            leftStart = leftStart.next;
            tail.next = null;
        } else {
            tail.next = rightStart;
            tail = tail.next;
            rightStart = rightStart.next;
            tail.next = null;
        }
    }
    if (leftStart == null) {
        tail.next = rightStart;
        listTail = tail;
        while (listTail.next != null) listTail = listTail.next;
    } else {
        tail.next = leftStart;
        listTail = tail;
        while (listTail.next != null) listTail = listTail.next;
    }
    return new ListNode[]{root.next, listTail};
}