Java:如何在链表中添加(中间某处)多个元素？

Question

已知向链表添加元素的时间复杂度为 O(1)。

但是，将其添加到位置 X 的复杂度为 O(X) 如果我想在这个位置添加 R 元素，总运行时间将为 O(R*X)。

但必须有一个 O(X+R) 解。

问题是如何在java中执行O(R+X)？

Answer 1

您有一个对 (element, X) 的列表，其中 X 是索引，element 是您要放入的项目那个索引。按 X 对此列表进行排序，并使用 Iterator 逐个添加元素。这是一个例子:

您的输入是:[(E1, 5), (E2, 3), (E3, 7)]。

1. 按索引排序:[(E2, 3), (E1, 5), (E3, 7)]

2. 创建一个迭代器并将其前进 3。

3. 使用迭代器添加 E2。

4. 将同一迭代器前进 2 (5 - 3)。

5. 添加E1。

6. ...

请注意，该算法有一个单数错误。修复它应该相对容易。

更新:刚刚注意到你的问题要简单得多。在您的情况下，只需创建一个迭代器，将其前进 X 次，然后使用该迭代器一一添加元素。