从链表中删除具有特定值的节点的代码无法删除所有节点

Question

我正在做这个任务：

将元素（1-50 范围内的数字）作为用户的输入，并使用这些元素创建一个链接列表。然后删除所有值大于 25 的节点。

给出了

LinkedList

类，包括

add(int value)

、

get(int index)

和

remove(int index)

方法。我必须实现逻辑来创建一个包含输入值节点的链表实例，然后有条件地从该链表中删除节点。

这是我的代码：

import java.util.*;

public class q1 {
  public static void main(String[] args) {

    LinkedList list = new LinkedList<Integer>();

    Scanner sc = new Scanner(System.in);

    for (int i = 0; i <= 10; i++) {
      list.add(i, sc.nextInt());
    }

    System.out.println(list);

    for (int i = 0; i < list.size(); i++) {
      if ((int) list.get(i) > 25) {
        list.remove(i);
      }
    }

    System.out.println(list);
  }
}

每当我运行此代码时，我仍然会在结果列表中得到大于 25 的值。

这是我输入的：

[23, 45, 12, 34, 34, 66, 25, 13, 12, 24, 33]

这是我得到的输出：

[23, 12, 34, 25, 13, 12, 24]

请注意结果中仍然存在不应该存在的值 34。

我的代码有什么问题？

Answer 1

问题是，当您删除索引

i

处的节点时，下一个节点（具有索引

i+1

）将位于该索引

i

，但您的循环仍然增加

i

，这意味着这个“ next”节点永远不会被检查。

实际上，这意味着如果您有两个连续节点的值大于 25，则只会删除这两个中的第一个。

有很多方法可以解决这个问题，但快速解决方法是让

i

从末尾开始，并使其向开头移动（到 0）：

for (int i = list.size() - 1; i >= 0; i--) {
  if ((int) list.get(i) > 25) {
    list.remove(i);
  }
}

现在它会产生预期的结果。

尽管如此，这个算法仍然不是很高效，因为

.get(i)

每次都必须从头开始迭代列表，使得该算法的时间复杂度为 O(𝑛²)。这不是最佳选择。

更好的是编写一个函数，它将在列表中迭代一次，并在单次遍历期间删除节点（在特定条件下）。那么时间复杂度将为 O(𝑛)。

Answer 2

问题是您正在修改

LinkedList

，同时循环其原始大小，在删除元素后会发生变化，实习生会导致循环内的索引指向不正确的值

如果我们用可视化的方式来看就会更清楚

INDEX    0   1   2   3   4   5   6   7   8   9  10
       [23, 45, 12, 34, 34, 66, 25, 13, 12, 24, 33]
         i

SIZE    11

当循环开始时，会显示

size

 中的 

i

 和 

LinkedList

 位置。

当在位置 1 找到大于 25 的元素时，让我们看看会发生什么

INDEX    0   1   2   3   4   5   6   7   8   9
       [23, 12, 34, 34, 66, 25, 13, 12, 24, 33]
             i

SIZE    10

正如我们从可视化中看到的，

size

 现在是 10，

i

 是 1

从这里我们可以看出几个问题

在循环的下一次迭代中，它将跳过当前应检查的
• i

  位置的元素

每次发现大于 25 的元素时，都会一次又一次地发生相同的过程，下一个元素将不会被验证，并且即使它大于 25，也会保留在

LinkedList

 中

要解决@tricot的状态问题，您可以从末尾开始循环

LinkedList

for (int i = list.size() - 1; i >= 0; i--) {
  if ((int) list.get(i) > 25) {
    list.remove(i);
  }
}

这导致时间复杂度为

O(𝑛²)

。

更好的方法是创建

ListIterator

 并使用它来删除 

LinkedList

 中大于 25 的元素，这将给出 

O(𝑛) 的时间复杂度

ListIterator<Integer> it = list.listIterator();
while (it.hasNext()) {
  if (it.next() > 25) {
    it.remove()
  }
}

参考

ListIterator

可以在

这里找到

Answer 3

更简单的解决方案只是添加一个 else:-

for(int i=0;i

        if(list.get(i)>25){

            list.remove(i);
        }else{
            ++i;
        }
    }