Leetcode - 148. 排序链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {

    // 1. 自顶向下的归并排序（可以用递归实现）：
    //    - 使用快慢指针找到链表的中点，将链表断成两截
    //    - 分别对两个子链表进行排序后，将这两个排序后的链表合并
    // 2. 自底向上的归并排序（本题采用的方式，可以用迭代方式实现，以 4 -> 2 -> 1 -> 3 为例）：
    //    - 先将链表分成若干个长度为1的链表：4, 2, 1, 3
    //    - 然后合并相邻的两个长度为1的链表：2 -> 4, 1 -> 3
    //    - 然后合并相邻的两个长度为2的链表：1 -> 2 -> 3 -> 4
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // 先测出链表的长度
        int length = 1;
        ListNode cur = head.next;
        while (cur != null) {
            length++;
            cur = cur.next;
        }

        // 在链表前添加一个节点，方便后续操作
        ListNode dummy = new ListNode();
        dummy.next = head;

        // subLength代表要合并的两个链表的长度，每次循环结束subLength变为原来的两倍
        // 也就是说，最开始先合并相邻的两个长度为1的链表；下一轮循环再合并相邻的两个长度为2的链表
        for (int subLength = 1; subLength < length; subLength <<= 1){
            
            // sortedTail和unsortedList的含义：
            // 1. 从dummy到sortedTail部分是在这轮循环中已经排好序了的部分
            // 2. 从unsortedList开始的部分是在这轮循环中还未排好序的部分
            ListNode sortedTail = dummy, unsortedList = dummy.next;
            while (unsortedList != null) {
                
                // 从unsortedList中切分出两个长度为subLength的链表l1和l2
                ListNode l1 = unsortedList;
                ListNode l2 = split(l1, subLength);
                
                // 切分出两个链表后，更新unsortedList
                unsortedList = split(l2, subLength);
                
                // 对切分出来的两个链表进行合并
                ListNode mergedList = mergeSortedList(l1, l2);
                
                // 将合并后的链表添加到sortedTail后面，并更新sortedTail
                sortedTail.next = mergedList;
                while (sortedTail.next != null) {
                    sortedTail = sortedTail.next;
                }
                
                // 将有序部分和无序部分（即未排序部分）重新连接起来
                sortedTail.next = unsortedList;
            }
        }
        return dummy.next;
    }

    // 切分链表，将链表的前length个节点切分出来；不妨假设链表为：1 -> 2 -> 3 -> 4
    // 如果length为2，则该方法将会把节点2的next置为null，并返回节点3
    private static ListNode split(ListNode head, int length) {
        if (head == null) {
            return null;
        }
        
        ListNode tail = head;
        int count = 1;
        while (tail != null && count < length) {
            tail = tail.next;
            count++;
        }

        // 如果tail为空，说明链表head的长度不足length，此时直接返回null
        if (tail == null) {
            return null;
        }
        
        // 否则将tail的next置为null，并返回原来的tail.next
        ListNode ret = tail.next;
        tail.next = null;
        return ret;
    }

    // 合并两个排序好了的链表
    private static ListNode mergeSortedList(ListNode l1, ListNode l2){
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        
        ListNode dummy = new ListNode(), cur = dummy, cur1 = l1, cur2 = l2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else{
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        cur.next = (cur1 == null) ? cur2 : cur1;
        return dummy.next;
    }
}