从`LinkedList`中删除元素

Question

各位，我的代码必须从列表中删除某个元素。它必须删除列表中出现的所有内容。例如，如果我想删除

"3"

并且输入是：

1
2
3
4
3
5

那么输出应该是：

1
2
4
5

但是我的代码仅删除最后一次出现的元素，正如我运行代码时可以看到的那样：

3
4
3
2
1

After removing element 3 


 4
 3
 2
 1

smb 可以帮我解决这个问题吗？预先感谢！

public void removeElements(String number){
        if(isEmpty()){
            System.out.println("The list is empty!");
        }
        else{
            if(firstLink.data.equals(number)){
                firstLink = firstLink.next;
            }
            else{
                Link current = firstLink.next;
                Link previous = firstLink;
                while(current != null){
                    if(current.data.equals(number)){
                        previous.next = current.next;
                        break;
                    }
                    else{
                        previous = current;
                        current = current.next;
                    }
                }
            }
        }
    }

Answer 1

删除元素的循环在第一场比赛时中断。也许像下面这样的东西会更好。当 current 匹配时，更新 previous.next 但保留 previous 指向前一个节点，当不匹配时，更新 previous 以指向当前节点。

while (current != null) {
    if (current.data.equals(number)) previous.next = current.next;
    else previous = current;
    current = current.next;
}

Answer 2

删除

break

，你的循环在第一次进入后就会中断。

另一点是，它落在你的

if(firstLink.data.equals(number))

中并完全忽略

else

块。您不应该在

else

中放置该块。应该在外面。

    if(firstLink.data.equals(number)){
        firstLink = firstLink.next;
    }
    Link current = firstLink.next;
    Link previous = firstLink;
    while(current != null){
       if(current.data.equals(number)){
          previous.next = current.next;
       } else {
            previous = current;
            current = current.next;
       }
   }

Answer 3

你可以做的是迭代整个循环并检查元素的值是否与搜索到的值匹配。如果是，那么您可以使用删除该元素。我不会透露这个问题的解决方案，但我可以为您提供算法。

for(int i = 0; i < length of list; i++)
{
    if(ith element of the list == value to be removed)
        //remove the ith term using .remove(i) method     
}

Answer 4

您可以做的是创建一个新集合，其中包含要从 LinkedList 中删除的所有值，然后在列表上调用removeAll：

ArrayList<String> numbersToRemove = new ArrayList<String>();
numbersToRemove.add("3");

list.removeAll(numbersToRemove);

这样，如果您以后想删除多个号码，只需将它们添加到numbersToRemove 即可。

其他一些答案更简单、更直接，因此，如果它们有意义，请使用它们，例如迭代列表并删除与要删除的元素匹配的任何元素。唯一的问题是，如果您在使用 object : list 语法迭代列表时修改列表，您将得到一个 ConcurrentModificationException 异常，并且如果您使用索引迭代它，可能会得到一个索引超出范围异常，所以您将可能需要做这样的事情：

while (list.contains("3")) {
    ll.remove("3");
}

Answer 5

您可以使用递归方法删除具有给定值的节点。

1. 基本条件 -> 对于空输入返回空
2. 在当前节点，我们将检查其是否有效节点， a] 如果其有效节点（即当前节点值！=给定值） 然后我们将通过列表中前面的有效节点设置它的“下一个”并且 返回当前节点 b] 如果它不是一个有效的节点， 我们只需返回列表中前面的有效节点

这是我上面讨论的方法的 C++ 实现， 只需将列表头和值传递给函数 -

ListNode* removeElements(ListNode* currentNode, int val) {

       //base condition
        if(currentNode==NULL) return NULL;

        // find nextValidNode
        ListNode* nextValidNode = removeElements(currentNode->next, val);

        // currentNode is NOT VALID node
        if(currentNode->val==val){
            return nextValidNode;
        }

        // currentNode is VALID node
        else{
            currentNode->next = nextValidNode;
            return currentNode;
        } 
}

其中ListNode是这样定义的-

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};