如何在链表中指定元素之前插入一个元素,使得时间复杂度为n。 例如 我想在 7 之前插入 100
LinkedList<Integer> linkedList = new LinkedList<>();
for (int i = 1; i <= 10; i++) {
linkedList.add(i);
}
我可以这样做
int index = linkedList.indexOf(7);
if (-1 != index) {
linkedList.add(index, 100);
}
但是我这样就遍历了链表两次了。
其实我们只要遍历一次就可以做到这一点。
那么我该怎么做呢?
PS:使用LinkedList即可
最佳答案
有一种方法可以使用ListIterator
一次性完成此操作。 ListIterator
与常规 Iterator
类似,只是您可以更改迭代方向,并且可以在当前位置添加
元素;请参阅javadoc .
所以代码是这样的:
LinkedList<SomeType> list = ...
SomeType a, b = ..
// Insert 'b' before the first element equal to 'a' in 'list'
ListIterator<SomeType> iterator = list.listIterator(0);
while (iterator.hasNext()) {
SomeType e = iterator.next();
if (e.equals(a)) {
iterator.previous(); // returns 'e' again. But the real purpose
// is to reset the iteration position
// so that 'next()' would return 'e' again.
iterator.add(b); // inserts before 'next()'.
break;
}
}
ListIterator::add
操作是一个“可选”操作,但它受 LinkedList
支持。 LinkedList
javadoc假设上面的内容不会导致 ConcurrentModificationException
。
关于java - 在链表中指定元素之前插入一个元素,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55886827/