你不需要重新排序它们。因为每个列表都已经排序过了，你可以按如下方式合并它们。它使用一个方法根据它们的相对值合并两个列表。然后它返回那个列表并将它反馈给方法，以将它与下一个列表合并。

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Merging {

    public static void main(String[] args) {
        List<Integer> list1 = List.of(5,10,15,20,25,30,35,40,45,50);
        List<Integer> list2 = List.of(2,4,6,8,10);
        List<Integer> list3 = List.of(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20);
        
      
        int nth = 10;
        List<List<Integer>> lists = List.of(list1,list2,list3);
        List<Integer> merged = lists.get(0);
        for (int i = 1; i < lists.size(); i++) {
            merged = mergeLists(merged, lists.get(i));
        }
        System.out.println(merged.get(nth));
    }

印刷品

7

• 这适用于实现Comparable接口的任何类型。
• 它将一直循环，直到一个列表用尽或两个索引都超过组合列表大小。
• 一旦任一列表完成，就可以通过子列表追加另一个列表。

public static <T extends Comparable<? super T>> List<T> mergeLists(List<T> list1, List<T> list2) {
        List<T> merged = new ArrayList<>();
        int i1 = 0;
        int i2 = 0;
        while (i1 + i2 < list1.size() + list2.size()) {
            if (i1 >= list1.size()) {
                merged.addAll(list2.subList(i2,list2.size()));
                break;
            }
            if (i2 >= list2.size()) {
                merged.addAll(list1.subList(i1,list1.size()));
                break;
            }
            if(list1.get(i1).compareTo(list2.get(i2)) <= 0) {
                 merged.add(list1.get(i1++));
            } else {
                merged.add(list2.get(i2++));
            }
        }
        return merged;
    }
}

这是一个相对高效（与列表数量呈线性关系）的算法，它利用了流的一些功能，但避免了完全的列表合并。

EDIT：为了解决数组长度检查、数组破坏和可读性等缺点，我改进了这个例子。为了更好地进行比较，我使用了与另一个答案相同的整数测试数据。

这个由（大概）不可变数组支持的虚拟队列将不会发生变化或其他情况

public class VirtualQueue<T> {
    private List<T> list;
    private int index=0;
    public VirtualQueue(List<T> list) { this.list = list; }
    public boolean hasMore() { return index < list.size(); }
    public T pop() { return list.get(index++); }
    public T peek() { return list.get(index);}
}

（我怀疑用标准集合有更简单的方法来做到这一点）

List<Integer> list1 = List.of(5,10,15,20,25,30,35,40,45,50);
List<Integer> list2 = List.of(2,4,6,8,10);
List<Integer> list3 = List.of(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20);

List<VirtualQueue<Integer>> listList = List.of(
    new VirtualQueue<>(list1),
    new VirtualQueue<>(list2),
    new VirtualQueue<>(list3));

int n=10;
var value = IntStream.range(0,n)
        .mapToObj(i -> listList.stream()
            .filter(VirtualQueue::hasMore)
            .min(Comparator.comparing(l -> l.peek()))
            .get().pop())
        .skip(n-1).findFirst().get();
//value is now the nth item in a hypothetical merged list.

假设您有k排序列表，并且您需要从聚合列表中获得n（但合并列表本身不需要），那么这个问题可以在**O（n * log k）时间内解决，并且使用O（k）**额外空间。

注：

• • 如果下面的代码看起来太复杂，下面是其背后的基本原理。这种解决方案比直接比较每个列表中的元素（可以在this和this答案中观察到）性能更高，后者的时间复杂度O（n * k）（相对于 * O（n * log k）*）。适度的额外复杂度是性能提升的代价，请注意，它仍然是可维护的。
• • 如果您需要具体化合并后的排序列表（下面的解决方案不会这样做），您可以简单地将列表组合在一起，并通过List.sort()使用内置的Timsort算法实现。Timsort非常擅长发现排序后的运行，因此对由排序块组成的列表进行排序将具有线性时间复杂度。*

为了在O（n * log k）时间内解决该问题，我们可以维护一个PriorityQueue，它将总是具有k或更小的大小（ 因此入队/出队操作将具有O（log k）**的成本）。在开始时，应该通过添加来自每个List的第一个元素来初始化Queue。
然后我们需要执行n迭代在每个迭代步骤中，队列的Head元素应该被移除，并且源自同一列表的下一个元素应该被添加到队列（即，如果我们说来自第三列表的第7个元素看起来是队列头，那么在移除它之后，我们需要将来自第三列表的第八元素入队）。
为了能够跟踪每个元素来自哪个List，以及它在List中的索引是什么，我们可以定义一个自定义类型：

public class ElementWrapper<V extends Comparable<V>> implements Comparable<ElementWrapper<V>> {
    private V value;
    private int listIndex;
    private int elementIndex;
    
    // all-args constructor, getters
    
    @Override
    public int compareTo(ElementWrapper<V> o) {
        return value.compareTo(o.getValue());
    }
}

下面是查找n元素的算法的实现方法，如前所述，时间复杂度为O（n * log k），因为我们需要n迭代步骤，每一步的开销为O（log k），额外的内存只需要用来维护k元素的队列。

public static <T extends Comparable<T>> T getNElement(List<List<T>> lists, int n) {
    Queue<ElementWrapper<T>> queue = initializeWithFirstElements(lists);
    
    T result = null;
    int count = 1;
    
    while (!queue.isEmpty()) {
        ElementWrapper<T> current = queue.remove();
        
        if (count == n) { // target index was reached
            result = current.getValue();
            break;
        }
        count++;
        
        if (hasNext(current, lists)) {
            addNext(current, lists, queue);
        }
    }
    return result;
}

public static <T extends Comparable<T>> Queue<ElementWrapper<T>>
            initializeWithFirstElements(List<List<T>> lists) {
    
    Queue<ElementWrapper<T>> queue = new PriorityQueue<>();
    for (int i = 0; i < lists.size(); i++) {
        if (lists.get(i).isEmpty()) continue;
        queue.add(new ElementWrapper<>(lists.get(i).get(0), i, 0));
    }
    return queue;
}

public static <T extends Comparable<T>> boolean
            hasNext(ElementWrapper<T> current, List<List<T>> lists) {
    
    return current.getElementIndex() + 1 < lists.get(current.getListIndex()).size();
}

public static <T extends Comparable<T>> void
            addNext(ElementWrapper<T> current, List<List<T>> lists,
                    Queue<ElementWrapper<T>> queue) {
    
    ElementWrapper<T> next = new ElementWrapper<>(
        lists.get(current.getListIndex()).get(current.getElementIndex() + 1),
        current.getListIndex(),
        current.getElementIndex() + 1
    );
    queue.add(next);
}

• 用法示例：*

public static void main(String[] args) {
    List<List<Integer>> input =
            List.of(List.of(1, 3), List.of(),
            List.of(2, 6, 7), List.of(10), List.of(4, 5, 8, 9)
        );
    
    System.out.println(getNElement(input, 1));
    System.out.println(getNElement(input, 3));
    System.out.println(getNElement(input, 9));
}

• 输出：*
  ***注意：*根据您希望如何为第n个元素建立索引，getNElement()方法中的count变量应相应地进行初始化，例如，如果您希望使用基于1的索引，则使用1;如果您希望n基于0，则使用0。