将元素添加到链表中已知为O（1）。
但是，将其添加到位置X是O（X）如果我想在这个位置添加R个元素，那么总运行时间将是O（R*X）。
但是必须存在O（X+R）解。
问题是如何在java中实现O（R+X）？
您有一个对(element, X)的列表，其中X是索引，element是要放在该索引下的项。按X对该列表进行排序，然后使用Iterator逐个添加元素。这里有一个例子：
您的输入是：[(E1, 5), (E2, 3), (E3, 7)]。
-
按索引排序：
[(E2, 3), (E1, 5), (E3, 7)] -
创建一个迭代器并将其提前
3。 -
使用迭代器添加
E2。 -
将同一迭代器前进
2（5 - 3）。 -
添加
E1。 -
。。。
请注意，此算法有一个of by one错误。修复它应该相对容易。
更新：刚刚注意到你的问题要简单得多。在您的情况下，只需创建一个迭代器，将其提前X次，然后使用该迭代器逐个添加元素。
假设您使用的是java.util.LinkedList，则存在LinkedList.listIterator（）方法，该方法返回listIterator:
公共ListIterator ListIterator（int索引）
返回此列表中元素的列表迭代器（正确序列），从列表中的指定位置开始。[…]
列表迭代器是故障快速的：如果列表在结构上被修改在创建迭代器之后的任何时间，以任何方式列表迭代器自己的remove或add方法引发ConcurrentModificationException。[…]
您可以使用ListIterator.add（）在LinkedList:中间安全地添加一个项
无效添加（E E）
将指定的元素插入到列表中（可选操作）。[…]
例如，假设你想把list2放在list1的第5个位置，你可以通过以下操作来做到：
LinkedList list1 = ...;
LinkedList list2 = ...;
ListIterator it1 = list1.listIterator(5);
for (Object item : list2) {
it1.add(item);
}
将元素放入集合，然后可以使用addAll方法将它们全部添加。