在Java中从链表中删除节点

Question

我想写一个代码，处理链表。这个链表有些不同，因为它是一个键值对链表(单独)。链表应该为用户提供基本功能，例如检索链表的大小、检查键是否在链表中、插入和删除。似乎所有的功能都工作正常，除了删除。删除方法的代码正确运行，没有运行时错误，但它给我的结果不是我想要的。下面是我的代码:

public class SequentialSearch<Key,Value> {
    private int N;     // number of key-value pairs
    private Node head; // the linked list of key-value pairs
    private Node tail;
    // a helper linked list data type
    private class Node {
        private Key key;
        private Value val;
        private Node next;
        public Node(Key key, Value val, Node next) {
            this.key = key;
            this.val = val;
            this.next = next;
        }
        public void setNext(Node next) {
            this.next = next;
        }
    }
    public SequentialSearch() {
    }
    public int size() {
        if (head == null)
            return 0;
        else {
            Node x = head;
            while (x.next != null) {
                N++;
                x = x.next;
            }
        }
        return N;
    }
    public boolean isEmpty() {
        return size() == 0;
    }
    public boolean contains(Key key) {
        return get(key) != null;
    }
    public Value get(Key key) {
        for (Node x = head; x != null; x = x.next) {
            if (key.equals(x.key))
                return x.val;
        }
        return null;
    }
    public void put(Key key, Value val) {
        if (val == null) {
            delete(key);
            return;
        }
        for (Node x = first; x != null; x = x.next) {
            if (key.equals(x.key)) {
                x.val = val;
                return;
            }
        }
        first = new Node(key, val, first);
        N++;
    }
    public boolean delete(Key key) {
        Node curr = head;
        Node prev = null;
        boolean result = false;
        if(isEmpty())
            System.err.println("Error: The list is empty.");
        while(curr != null) {
            if(key.equals(curr.key)) {
                if(curr.equals(head)) {
                    head = curr = null;
                    N--;
                    result = true;
                    return result;
                } else {
                    prev.next = curr.next;
                    curr.setNext(null);
                    N--;
                    result = true;
                    return result;
                }
            } else {
                prev = curr;
                curr = curr.next;
            }
        }
        return result;
    }
}

我写了一个主程序来测试添加(放)和删除，但它似乎是为插入工作，而不是为删除工作。我想我可能会遇到一个问题在列表中只有一个节点的情况下删除，以及从列表中间删除一个节点的情况。

我也试图通过使用递归编写一个新方法来修改删除方法，但我面临一些错误-也是逻辑上的。下面是该函数的代码:

public void delete(Key key) {
    first = delete(first, key);
}
private Node delete(Node x, Key key) {
    if (x == null) return null;
    if (key.equals(x.key)) {
        N--;
        return x.next;
    }
    x.next = delete(x.next, key);
    return x;
}

你能告诉我我做错了什么吗?

Answer 1

head = curr = null;

这句话有点令人困惑，但我认为这可能是你在删除时的问题。如果你要删除'head'处的匹配，你只需要将head设置为' current .next'

我认为发生了什么:删除()

a -> b -> c -> d

head = a
curr = a
curr.next = b

您将head设置为null，但是head需要指向新列表中的第一项，如果您删除'a'，则该项将是'b'，或者current .next