在不使用任何 API 的情况下从 java 中的 LinkedList 中删除特定项目

Question

我正在尝试从java中的LinkedList中删除一个项目。此列表由我实现，我没有使用任何 java API。我面临的主要问题是递归，因为我总是迷失在递归编码中。

class List{
    int N;
    List next;
    List current;
    List(int N){
        this.N =N;
        this.next = null;
    }
    @Override
    public String toString() {
        String o = "";
        List curr = this;
        while(curr != null){
            o += curr.N+"-->";
            curr = curr.next;
        }
        return o+"TAIL";
    }
}

实施方法：

private static List Remove(List L,int N){
    if(L == null || L.next == null)
        return L;
    List current = L;
    List previous = null;
    while(current != null){
        if(current.N == N){
            current = current.next;
            if(previous == null)previous = current;
            else{
                previous.next = current;
            }
            break;
        }else{
            previous = current;
            current = current.next;             
        }   
    }
    return previous;
}

输入-

List list1 = new List(1);
        list1.next = new List(2);
        list1.next.next = new List(3);
        list1.next.next.next  = new List(4);
        list1.next.next.next.next  = new List(5);
        list1.next.next.next.next.next  = new List(6);
        list1.next.next.next.next.next.next  = new List(7);
System.out.println("Before Removal "+list1.toString());
        System.out.println("After Removal "+Remove(list1,3));

我得到的输出是 -

• 移除前 1-->2-->3-->4-->5-->6-->7-->尾
• 移除后 2-->4-->5-->6-->7-->尾

在这里，当我设置current = current.next或引用设置为下一个值时，我丢失了值 1。因此，我肯定在呈现存储在不同参考中的数据时遇到了一些问题。

Answer 1

错误在这里：

return previous;

如果未删除列表的原始标题

，则应返回列表的原始标题。要以图形方式显示它：

N == 3
List Before Removal: 1-->2-->3-->4-->5-->6-->7-->TAIL
At start of iteration 1:
L                    ^
previous      (null)
current              ^
No match -> iteration 2:
L                    ^
previous             ^
current                  ^
No match -> iteration 3:
L                    ^
previous                 ^
current                      ^
Match -> remove current:
List After Removal:  1-->2-->4-->5-->6-->7-->TAIL
L                    ^
previous                 ^
current                      ^

此时通过返回previous，您将失去以前的头部元素L。

对于要删除 head 元素的情况，您应该在循环之前添加单独的检查。

顺便说一句，你的Remove方法不是递归的 - 它永远不会调用自己。

Answer 2

这仅仅是因为你没有返回头部 - 而是返回你刚刚"删除"的节点的上一个指针：

static List Remove(final List L, final int N) {
    // Base case for null head pointer  
    final List head = L;
    if (head == null)
        return head;
    // Base case for removing the head
    if (head.N == N)
       return head.next;
    List current = head.next;
    List previous = head;
    while (current != null) {
        if (current.N == N) {
            current = current.next;
            if (previous == null) {
                previous = current;
            }
            else {
                previous.next = current;
            }
            break;
        } else {
            previous = current;
            current = current.next;
        }
    }
    return head;
}

另外 - 澄清一下 - 这不是递归解决方案。