java - 如何从链表java中删除特定值？

Question

public class LinkList
{
private Node list;
private int count;  // number of values stored in the list

public LinkList(){
    list = null;
    count = 0;
    }

// Returns number of values in the LinkList
public int count() {
    return count;
}



/*
 * delete all nodes with this value
 * if the count is zero do nothing
 * if count is 1 delete front node (can use front() and ignore return)
 * else travel the list and when found make prev.next cur.next ... return
 * if still in method delete rear node.
 *
 */


public void deleteNode(int value)
{

    }


}


public class Node{

int value;
Node next;

public Node() {
    next=null;
}

public Node(int n, Node nextNode){
    setValue(n);
    setNext(nextNode);
}

public int getValue(){
    return value;
}

public void setValue(int n){
    value = n;
}

public Node getNext(){
    return next;
}

public void setNext(Node node){
    next = node;
}

public boolean equals(Node other) {
    return (this.getValue() == other.getValue());
}

public String toString() {
    return "" + value;
}

}

Answer 1

                    +------+        +------+        +------+
                    |      |        |      |        |      |
            Step 0  |      |+------>|      |+------>|      |
                    |      |        |      |        |      |
                    |      |        |      |        |      |
                    +------+        +------+        +------+

                               +----------------+
                    +------+   |    +------+    |   +------+
                    |      |+--+    |      |    +-->|      |
            Step 1  |      |        |      |+------>|      |
                    |      |        |      |        |      |
                    |      |        |      |        |      |
                    +------+        +------+        +------+


                    +------+                        +------+
                    |      |                        |      |
            Step 2  |      |+---------------------->|      |
                    |      |                        |      |
                    |      |                        |      |
                    +------+                        +------+

Answer 2

首先，使用 Java 现有的ArrayList实现。对于大多数操作来说，它是O(n)线性时间，有些甚至是O(1). 它还与集合、迭代器和集合很好地集成。

我建议改用双向链表。只需添加一个previous包含所需 getter 和 setter 的字段。

然后要删除，只需将当前节点周围的前一个和下一个链接在一起。即留给读者作为练习。（或在修订历史中找到它）这只是将链接重新放在当前选定的节点周围。

如果要使用单链表，则必须遍历列表，并检查 next 是否是要删除的节点。然后将当前节点的下一个设置为 nextNode.getNext()。

后一种方法效率很低。

Answer 3

您想在值不为空时遍历您的链表。如果遇到要删除的值，请删除节点，重新处理链接，然后返回。您的函数应如下所示：

public void deleteNode(int value)
{
    if(count == 0) {
        return;
    } else if (count == 1){
        // delete this node. I'm not quite sure what you mean by use front() in your instruction
    } else {
        Node x = Node first; // This should be the first node in the list
        while(x != null && x.next != null) {
            if(x.value == value) {
                if(x == first) {
                    first = x.next; // If your first node is bad, make 2nd node your first node
                } else {
                    prev.next = x.next; // This skips the current node, with the sought-after value
                }
            } else {
                x = x.next; // Traverse to check the next node
            }
        }
    }
}

请记住，您需要在节点类中声明 prev 和 first 节点。不要以为我看到了给定代码中定义的那些。