牛客网：NC51 合并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 lists) {
        ListNode node = null;
        for (int i = 0; i < lists.size(); i++){
            node = merge(node, lists.get(i));
        }
        return node;
    }
    
    private ListNode merge(ListNode node1, ListNode node2){
        if (node1 == null) return node2;
        if (node2 == null) return node1;
        if (node1.val > node2.val) {
            node2.next = merge(node1, node2.next);
            return node2;
        }
        node1.next = merge(node1.next, node2);
        return node1;
    }
}

不行，时间复杂度过高。

在一的基础上添加分治，减少时间复杂度

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 lists) {
        return divideMerge(lists, 0 , lists.size() - 1);
    }
    
    private ListNode divideMerge(ArrayList lists, int left, int right){
        if (left > right){
            return null;
        }
        // 找到中间节点
        if (left == right){
            return lists.get(left);
        }
        int mid = (left + right) >> 1;
        return merge(divideMerge(lists, left, mid ), divideMerge(lists, mid + 1, right));
    }
    
    private ListNode merge(ListNode node, ListNode node2){
        if (node == null) return node2;
        if (node2 == null) return node;
        if (node.val > node2.val) {
            node2.next = merge(node, node2.next); 
            return node2;
        }
        node.next = merge(node.next, node2);
        return node;
    }
}