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 次，然后使用该迭代器一个一个地添加元素。