递归删除Java中的节点链表

Question

我正在学习数据结构，并试图理解Java中的链接列表。我的问题是，我有麻烦与删除节点在给定的索引递归。我的目标是得到O（log n），而不是使用循环，最后得到O（n）。

public class LinkedList {
    Node head;
    int index=0;
    Node temp;
    Node prev;
    public LinkedList(Node head){
        this.head=head;
        temp=head;
        prev=null;
    }
    public int length(){
        int counter=0;
        Node n= head.next;
        while(n!=null){
            counter=counter+1;
            n=n.next;
        }
        return counter;
    }
    public void push(Node newNode){
        newNode.next=head;
        head=newNode;
    }
    public void add(Node prevNode, int value){
        if(prevNode==null){
            System.out.println("The given previous node can not be null!");
            return;
        }
        Node newNode= new Node(value,null);
        newNode.next=prevNode.next;
        prevNode.next=newNode;
    }
    public void add(int index, int value){
        length();
        if((index<0)||(index>length())){
            System.out.println("Array out of bound!");
            return;
        }
        if(index==0){
            push(new Node(value,null));
            return;
        }
        Node newNode= new Node(value,null);
        Node prevNode=head;
            for(int i=1;i<index;i++){
            prevNode=prevNode.next;
        }
        newNode.next=prevNode.next;
        prevNode.next=newNode;
    }
    public void delete(){
        head=head.next;
    }
    public void delete(int index){
        if((index<0)||(index>length())){
            System.out.println("Array out of bound!");
            return;
        }
        if(index==0){
            delete();
        return;}
        if(head.next==null||head==null){
            head=null;
        return;}
        if(this.index!=index){
            this.index++;
            prev=temp;
            temp=temp.next;
            delete(index);
        }if(this.index==index){
            prev=temp.next;
        }
    }
    public void search(int value){
        if(head!=null){
        if(value!=head.value){
            head=head.next;
            index=index+1;
            search(value);
        }else if(value==head.value){
            System.out.println("The value \""+value+"\" was found in index: "+index);}}}
    public void display(){
        Node n= head;
        System.out.print("{");
        while(n!=null){
            System.out.print(" ("+n.value+") ");
            n=n.next;
        }System.out.print("}");
        System.out.println("\n------------------------------");
    }
    public static void main(String[]args){
        LinkedList ll= new LinkedList(new Node(2,null));
        ll.push(new Node(5,null));
        ll.push(new Node(6,null));
        ll.push(new Node(13,null));
        ll.push(new Node(1,null));
        ll.display();
        ll.add(ll.head.next,8);
        ll.display();
        ll.add(0, 0);
        ll.display();
        ll.add(6, 4);
        ll.display();
        System.out.println(ll.length());
        ll.search(13);
        ll.delete(2);
        ll.display();
    }
}

因此，当我试图删除索引2的条目时，它会删除该索引之前的所有数字，但不会删除该索引-因此它会删除[0]和[1]，但不会删除[2]。

例如，在此代码中，删除前的数组填充为：{0,1,13,8,6,5,4,2}。调用delete（2）后，它有以下条目：{13,8,6,5,4,2}

我只想删除13，这样数组就会像这样：{0,1,8,6,5,4,2}

我真的很感激任何改进代码的提示。

Answer 1

好的，让我们用一个例子来说明这个问题。这很简单，但一旦掌握了诀窍并理解了delete递归算法，就可以轻松地使示例类通用化，注意封装，优化代码，然后继续生产。

为了举例，假设基本的单个LinkedList和Node类非常简单。内部静态节点类仅存储基元int类型，并且它仅包含对列表中以下节点元素的next引用。LinkedList仅包含一个head节点，它是链接列表的开头。这不是双链接列表，也没有对上一个节点的引用。从给定的节点（通常为头部节点）到下一个参考，依次进行遍历。我已经为这两个应用程序都添加了一个toString（）实现，稍后将派上用场：

public class LinkedList {

protected Node head;

public LinkedList(Node head) {
    super();
    this.head = head;
}

static class Node {

    protected int data;
    protected Node next;

    Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Node ");
        builder.append(data);
        if (null != next)
            builder.append(" -> ");
        return builder.toString();
    }
}

@Override
public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append("LinkedList [");
    Node node = head;
    while (node != null) {
        builder.append(node);
        node = node.next;
    }
    builder.append("]");
    return builder.toString();
}

}

现在，让我们添加一个递归的delete（）方法。删除单链接列表中的节点只能通过从上一个节点的next引用中取消链接来完成。此规则的唯一例外是head节点，我们将其删除为空。因此，很明显，我们需要（除了起点当前节点引用之外）对前一个节点的引用。

因此，我们的递归删除（）方法签名可以是：

private LinkedList delete(Node node, Node prev, int key)

尽管此方法的返回类型可以完全省略（void），但支持链功能非常有用，因此API调用可以成为一个线性的点分隔语法，例如：

System.out.println(list.push(0).append(2).deleteAll(1));

因此，为了链的能力，我们也将从这个方法返回对整个LinkedList实例的引用。根据参数列表：

第一个参数是要检查它是否与给定的键匹配的当前节点。下一个参数是前一个节点，以防我们需要取消当前节点的链接。最后一个参数是我们在所有要删除（取消链接）的节点中查找的键。

方法修饰符是私有的，因为它不打算公开使用。我们将用用户友好的facade方法包装它，该方法将以head作为当前节点和null作为前一个节点开始递归：

public LinkedList deleteAll(int key) {
    return delete(head, null, key);
}

现在，让我们看看我们如何实现递归删除（...）方法，我们从终止递归的两个基本条件开始；空当前节点或列表中的单个节点，这也是head节点：

private LinkedList delete(Node node, Node prev, int key) {
    if (node == null)
        return this;
    if (node == head && head.data == key && null == head.next) { // head node w/o next pointer
        head = null;
        return this;
    }
    //...more code here
}

达到第一个基本条件意味着我们已经到达链表的末尾（是否找到了键），或者链表是空的。我们完成了，并返回对链接列表的引用。

第二个基本条件检查当前节点是否为头部节点，以及它是否与键匹配。在本例中，我们还检查它是否恰好是链表中的单个节点。在这种情况下，头部节点需要进行“特殊”处理，必须分配null，才能删除。当然，在删除head节点后，列表为空，我们就完成了，因此我们返回对链接列表的引用。

下一个条件检查当前节点是否匹配键，如果它是头节点，但在列表中不是单独的。

private LinkedList delete(Node node, Node prev, int key) {
    //...previous code here
    if (node == head && head.data == key) { // head with next pointer
        head = head.next;
        return delete(head, null, key);
    }
    //...more code here
}

我们稍后将优化此代码，但现在，在这种情况下，我们只需向前一步将引用移动到head，因此head将被有效删除（旧引用将被垃圾收集），并且我们将新的head作为当前节点重复，而null仍然是前一个节点。

下一个案例涵盖了匹配键的常规（中间或尾部）节点：

private LinkedList delete(Node node, Node prev, int key) {
    //...previous code here
    if (node.data == key) {
        prev.next = node.next;
        return delete(prev, null, key);
    }
    //...more code here
}

在这种情况下，我们通过取消当前节点上一个节点的下一个指针的链接并将其分配给当前节点地址来删除当前节点。我们基本上跳过当前节点，它变成了垃圾。然后，我们重复使用前一个节点作为当前节点，空作为前一个节点。

在所有这些处理过的案例中，我们都与键匹配。最后，我们处理不匹配的情况：

private LinkedList delete(Node node, Node prev, int key) {
    //...previous code here
    return delete(node.next, node, key);
}

显然，我们重复使用下一个节点作为当前节点，旧的当前节点作为前一个节点。键在所有递归调用中保持不变。

整个（未优化）方法现在如下所示：

private LinkedList delete(Node node, Node prev, int key) {
    if (node == null)
        return this;
    if (node.data == key && node == head && null == node.next) { // head node w/o next pointer
        head = null;
        return this;
    }
    if (node.data == key && node == head) { // head with next pointer
        head = head.next;
        return delete(head, null, key);
    }
    if (node.data == key) { // middle / tail
        prev.next = node.next;
        return delete(prev, null, key);
    }
    return delete(node.next, node, key);
}

如果使用尾部递归，许多编译器（包括javac）可以优化递归方法。当递归调用是该方法最后执行的事情时，递归方法是尾部递归的。然后，编译器可以用一个简单的goto/label机制替换递归，并为每个递归帧节省运行时所需的额外内存空间。

我们可以轻松地优化递归delete（…） 要遵守的方法。我们可以保留对当前节点和上一个节点prev的引用，并在每个案例处理中为它们分配适当的值，而不是从每个已处理的条件（案例）递归返回。这样，唯一的递归调用将发生在方法的末尾：

private LinkedList delete(Node node, Node prev, int key) {
    if (node == null)
        return this;
    if (node.data == key && head == node && null == node.next) { // head node w/o next pointer
        head = null;
        return this;
    }
    Node n = node.next, p = node;
    if (node.data == key && head == node) { // head with next pointer
        head = head.next;
        n = head;
        p = null;
    } else if (node.data == key) { // middle / tail
        prev.next = node.next;
        n = prev;
        p = null;
    }
    return delete(n, p, key);
}

我添加了一个简单的maintestdriver方法来测试delete（…） 方法实现，通过facade方法deleteAll（…） ：

public static void main(String[] args) {
    LinkedList list = new LinkedList(new Node(0, new Node(1, new Node(1, new Node(2, new Node(2, new Node(3, null)))))));
    System.out.println(list);
    System.out.println(list.deleteAll(6));
    System.out.println(list.deleteAll(1));
    System.out.println(list.deleteAll(3));
    System.out.println(list.deleteAll(2));
    System.out.println(list.deleteAll(0));
}

输出（使用我提供的toString（）方法）是：

LinkedList [Node 0 -> Node 1 -> Node 1 -> Node 2 -> Node 2 -> Node 3]
LinkedList [Node 0 -> Node 1 -> Node 1 -> Node 2 -> Node 2 -> Node 3]
LinkedList [Node 0 -> Node 2 -> Node 2 -> Node 3]
LinkedList [Node 0 -> Node 2 -> Node 2]
LinkedList [Node 0]
LinkedList []
 

虽然从第一篇文章开始已经三年了，但我相信其他一些Java程序员，如果不是OP的话，会觉得这个解释很有用。

Answer 2

经过努力，我设法解决了这个问题，这是答案，但我仍然不确定它的复杂性是O（n）还是O（log n）。

 public void delete(int index){
        //check if the index is valid
        if((index<0)||(index>length())){
            System.out.println("Array out of bound!");
            return;
        }
        //pass the value head to temp only in the first run
        if(this.index==0)
            temp=head;
        //if the given index is zero then move the head to next element and return
        if(index==0){
            head=head.next;
        return;}
        //if the array is empty or has only one element then move the head to null
        if(head.next==null||head==null){
            head=null;
        return;}
        if(temp!=null){
            prev=temp;
            temp=temp.next;
            this.index=this.index+1;
            //if the given index is reached
           //then link the node prev to the node that comes after temp
          //and unlink temp
            if(this.index==index){
                prev.next=temp.next;
                temp=null;
                return;
            }
         //if not then call the function again
           delete(index);
        }
    }

Answer 3

理解代码是非常困难的，但由于您需要逻辑来提高理解能力，所以共享psuedocode，您可以参考它来相应地更正代码。

Node delete (index i, Node n) // pass index and head reference node and return head
   if (n==null) // if node is null
      return null;
   if (i==1)  // if reached to node, which needs to be deleted, return next node reference.
      return n.next;  
   n.next= delete(n.next,i-1);
   return n; // recursively return current node reference