题解 | #合并k个已排序的链表#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here

        // 算法时间复杂度O(NlogN)，额外空间复杂度O(logN)

        // 分治思想，参考归并排序，K个链表可以两两合并，新合并的链表再两两合并，直到K个链表全部合并
        // 这道题的重点就是把lists的划分合并区间函数的递归调用写出来
        return divideMerge(lists, 0, lists.size() - 1);
    }

    // 划分合并区间函数
    ListNode divideMerge(ArrayList<ListNode> lists, int left, int right) {
        // 递归出口 - 划分到没法再分为止
        if (left > right) {
            return null;
        }
        else if (left == right) {
            return lists.get(left);
        }

        // 重点！从中间分成两段，再将合并好的两段合并
        int mid = (left + right) / 2;
        return Merge(
            divideMerge(lists, left, mid), 
            divideMerge(lists, mid + 1, right)
            );
    }

    // 两个链表合并函数 - 上一道题的过程
    public ListNode Merge(ListNode pHead1, ListNode pHead2) {
        // 算法时间复杂度O(N)，额外空间复杂度O(1)

        // 1.处理边界情况，确保两个链表非空
        if (pHead1 == null) {
            return pHead2;
        }
        if (pHead2 == null) {
            return pHead1;
        }

        // 2.找到两个有序链表头结点中较小的那个，记为targetHead，以target链表为合并的容器，另外一个链表记为source链表
        ListNode targetHead;
        ListNode sourceHead;
        if (pHead1.val <= pHead2.val) {
            targetHead = pHead1;
            sourceHead = pHead2;
        } else {
            targetHead = pHead2;
            sourceHead = pHead1;
        }

        // 3.遍历target链表，针对每个targetCur结点，去source中尝试找到这样一个子序列：
        //      该子序列的所有结点满足 >= targetCur 且 < targetNext(targetCur.next)
        // 若能够找到，则用sourceStart和sourceEnd固定其头和尾的位置，然后将这个子序列完整纳入到target链表中
        ListNode targetCur = targetHead;
        ListNode targetNext = targetHead.next;
        ListNode sourceCur = sourceHead;
        ListNode sourceStart = null;
        ListNode sourceEnd = null;
        while (targetCur != null) {
            System.out.println("targetCur: " + targetCur.val);
            targetNext = targetCur.next;
            if (sourceCur != null && sourceCur.val >= targetCur.val) {
                // 3.1 发现了source链表中有一个 >= targetCur的结点，先记为sourceStart
                // 注意！sourceStart可能已经 >= targetNext的，这种情况是不能将其纳入的，后续要对这种情况做好判断！
                sourceStart = sourceCur;
                System.out.println("发现了一个source链表中比targetCur大的结点：" +
                                   sourceStart.val);
                if (targetNext == null) {
                    // 3.2 如果targetCur没有下一个结点，那么sourceStart及其后续结点必然满足要求
                    // 此时就会把从sourceStart开始剩余的source结点全部纳入进来，可以直接结束
                    System.out.println("此时target链表已经到了最后一个结点了");
                    targetCur.next = sourceStart;
                    break;
                }

                // 3.3 如果targetCur还有下一个结点，那么必须找到 >= targetCur，且 < targetNext的source结点
                while (sourceCur.next != null && sourceCur.next.val < targetNext.val) {
                    // 找到source链表中一系列比targetCur大，且比targetNext小的source结点，确定它们的头和尾
                    // 注意！sourceCur可能本身已经 >= targetNext了，结束while循环后一定要做对应判断！
                    sourceCur = sourceCur.next;
                }
                sourceEnd = sourceCur;
                // 3.4 此时存在一种可能，即只有唯一的sourceCur，确实 >= target，但是它同时 >= targetNext，此时不应该纳入，应该提前迭代
                if (sourceEnd.val >= targetNext.val) {
                    System.out.println("虽然 >= targetCur，但它同时 >= targetNext，此时也不应该放入");
                    targetCur = targetNext;
                    continue;
                }
                sourceCur = sourceCur.next;
                // 3.5 找到了sourcr链表中满足条件的子序列，且以sourceStart开头，sourceEnd结尾，将他们整体纳入到target链表中
                targetCur.next = sourceStart;
                sourceEnd.next = targetNext;
            }
            // 3.6 target迭代遍历
            targetCur = targetNext;
        }
        return targetHead;
    }
}