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

import java.util.*;

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

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

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类一维数组 
     * @return ListNode类
     */
     /**
     * 合并两个有序链表
      */
    public ListNode merge(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) return l1 == null ? l2 : l1;
        ListNode newHead = new ListNode(-1);
        ListNode tmp = newHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                tmp.next = l1;
                l1= l1.next;
            } else {
                tmp.next = l2;
                l2 = l2.next;
            }
            tmp = tmp.next;
        }

        if (l1 != null) tmp.next = l1;
        if (l2 != null) tmp.next = l2;

        return newHead.next;
    }
    public ListNode mergeKLists (ListNode[] lists) {
        // write code here
        // 思路：归并思路22合并最终为1
        // 1. 处理特殊情况
        if (lists == null || lists.length <= 0) return null;
        // 2. 开始归并（与归并排序类似）
        me(lists,0,lists.length - 1);
        // 3. 每次二路归并后将合并后的链表存在最左边
        return lists[0];
    }

    public void me(ListNode[] lists, int left, int right) {
        // 1. 递归结束条件
        if (left >= right) {
            return;
        }

        // 2. 计算中间位置
        int mid = (left + right) / 2;
        // 3. 递归左边
        me(lists, left,mid);
        // 4. 递归右边
        me(lists,mid + 1,right);
        // 5. 左右合并（每次都将合并后的链表存储在当前段的最左）
        lists[left] = merge(lists[left],lists[mid + 1]);
    }
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        ListNode[] list = (ListNode[])lists.toArray(new ListNode[lists.size()]);
        return mergeKLists(list);
    }
}