在Java中删除LinkedList中的特定项目而不使用任何API

Question

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

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 - > TAIL
• 后去除2 - > 4 - > 5 - > 6 - > 7 - > TAIL

这里我失去值1，因为我设置current = current.next或参考正被设置为下一个值。所以当然，我对存储在不同引用中的数据的表示存在一些问题。

Answer 1

的错误是在这里：

return previous; 

如果不删除它，您应该返回列表的原厂头。要以图形方式显示它：通过返回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     ^

在这一点上，你失去了前head元素L。

对于头部元件要被移除的情况，您应该在循环前添加一个单独的检查。

btw你的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; 
} 

而且 - 澄清 - 这不是一个递归解决方案。