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

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

// 归并思想 + 基础两两链表相加操作
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        
        return divideMerge(lists,0,lists.size()-1);

    }

    // 归并思想
    public 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 mergeTwo(divideMerge(lists,left,mid),divideMerge(lists,mid+1,right));
    }

    // 两两链表合并操作
    public ListNode mergeTwo(ListNode list1,ListNode list2){
        
        // 先判断是否有数据
        if(list1 == null || list2 == null){
            if(list1 == null){
                return list2;
            }else if(list2 == null){
                return list1;
            }
        }

        // 设置返回头
        ListNode head = new ListNode(-1001);

        // 设置i
        ListNode i = head;

        // 双方都有数据时进行比较大小并改变next
        while(list1 != null && list2 != null){

            if(list1.val > list2.val){

                i.next = list2;

                i = i.next;

                list2 = list2.next;
                
            }else{
                i.next = list1;

                i = i.next;

                list1 = list1.next;
            }

        }

        // 无数据时直接将另一方加入链表即可
        if(list1 == null){
            i.next = list2;
        }else{
            i.next = list1;
        }

        return head.next;

    }
}