148. Sort List

MergeSort

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummyHead = new ListNode(-1, head);
        // d, 1, 2, 3, 4
        //             f
        //       s

        // d, 1, 2, 3, 4, 5
        //                  f
        //          s

        ListNode fast = dummyHead, slow = dummyHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        ListNode next = slow.next;
        slow.next = null; // 切断链表

        ListNode leftHead = sortList(head), rightHead = sortList(next);
        ListNode curr = dummyHead;
        while (leftHead != null && rightHead != null) {
            if (leftHead.val < rightHead.val) {
                curr.next = leftHead;
                leftHead = leftHead.next;
            } else {
                curr.next = rightHead;
                rightHead = rightHead.next;
            }
            curr = curr.next;
        }

        curr.next = leftHead != null ? leftHead : rightHead;
        
        return dummyHead.next;
    }
}

MergeSort

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        int length = getLength(head);

        for (int pieceLength = 1; pieceLength < length; pieceLength *= 2) {
            ListNode pre = dummyHead;
            ListNode curr = pre.next; // 注意每轮的起点为 pre.next, 不能为 head, 因为 head 可能被交换到后面去了


            while (curr != null) { // 不要忘记这一层循环，因为一个链表中可能存在多对左右链表
                int i = pieceLength;
                ListNode l1 = curr;
                while (curr != null && i > 0) {
                    curr = curr.next;
                    i--;
                }

                if (i > 0) {
                    // 左侧的子链表元素个数不足 pieceLength 个，即不能构成左链表与右链表，无需执行下面的归并左右链表的逻辑，此时直接跳出 for 循环，如果 i 等于 0 说明当前节点位于右侧子链表的首个节点，需要归并排序
                    break;
                }

                ListNode l2 = curr;
                i = pieceLength;
                while (curr != null && i > 0) {
                    curr = curr.next;
                    i--;
                }

                ListNode nextPairStartNode = curr;

                int l1Length = pieceLength, l2Length = pieceLength - i; // 到此处时 l1 长度肯定为 pieceLength, l2 则为 pieceLength - i
                // 根据左右子链表的长度进行归并，注意不能使用 next, 因为我们没有将两个子链表切断
                while (l1Length > 0 && l2Length > 0) {
                    if (l1.val < l2.val) {
                        pre.next = l1;
                        l1 = l1.next;
                        l1Length--;
                    } else {
                        pre.next = l2;
                        l2 = l2.next;
                        l2Length--;
                    }
                    pre = pre.next;
                }

                // 当两个子链表长度不等时处理较长的链表部分
                pre.next = l1Length > 0 ? l1 : l2;
                // 将 pre 继续在子链表上移动，移动至子链表的尾节点
                while (l1Length > 0 || l2Length > 0) {
                    pre = pre.next;
                    l1Length--;
                    l2Length--;
                }

                // 当前 pre 指向的合并后的链表的尾节点，注意该节点可能含有 next 指针，所以我们校正该 next 指针指向下一对链表的头节点
                pre.next = nextPairStartNode;
            }
        }

        return dummyHead.next;
    }

    private int getLength(ListNode node) {
        int length = 0;
        while (node != null) {
            length++;
            node = node.next;
        }
        return length;
    }
}

迭代法细节较多，想一次写对还是比较困难。

Reference

148. Sort List