在Java中递归删除节点链表
我正在学习数据结构，并试图理解Java中的链表。我的问题是我在递归删除给定索引处的节点时遇到了问题。我的目标是得到O(log )，而不是使用循环，最终得到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处的条目时，它会删除该索引之前的所有数字，但不会删除该索引上的所有数字-因此它删除的是和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}
我真的很感谢任何改善我代码的技巧。
回答 3
Stack Overflow用户
发布于 2018-09-23 02:13:47
理解你的代码是非常困难的，但由于你要求逻辑来提高你的理解，所以分享伪代码，你可以参考它来相应地纠正你的代码。
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 referenceStack Overflow用户
发布于 2018-09-23 05:27:31
经过努力，我终于解决了这个问题，这就是答案，但我仍然不确定它的复杂性是O(n)还是O(log )。
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);
}
}Stack Overflow用户
发布于 2021-10-07 18:06:11
链表中的Java递归删除方法
好的，让我们通过一个例子来了解一下。它很简单，但是一旦您掌握了它的诀窍并理解了delete递归算法，您就可以很容易地使示例类成为generic，负责封装，优化代码，然后继续生产。
本例中的类
为了举例，假设基本的单一LinkedList和Node类非常简单。内部静态Node类只存储基本的int类型，并且它只包含对列表中以下Node元素的next引用。LinkedList只包含一个head节点，它是链表的开始。这不是一个双向链表，并且它没有对前一个节点的引用。遍历顺序是从给定的Node (通常是头节点)到next引用，一个节点接着另一个节点。我已经为这两者添加了一个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节点，我们将其设为空以进行删除。因此，很明显，我们需要(除了起点current node引用之外)对上一个节点的引用。
因此，我们的递归delete()方法签名可以是：
private LinkedList delete(Node node, Node prev, int key)尽管此方法的返回类型可以完全省略(void)，但它对支持链式功能非常有用，这样API调用就可以成为单行的、点分隔的语法，例如：
System.out.println(list.push(0).append(2).deleteAll(1));因此，为了提高链接性，我们还将从该方法返回对整个LinkedList实例的引用。根据参数列表：
第一个参数是当前节点，检查它是否与给定的key匹配。下一个参数是前一个节点，以防我们需要取消当前节点的链接。最后一个参数是我们要在所有要删除(未链接)的节点中查找的键。
方法修饰符是private，因为它不打算公开使用。我们将它包装在一个用户友好的facade方法中，该方法将以head作为当前节点，null作为上一个节点开始递归：
public LinkedList deleteAll(int key) {
return delete(head, null, key);
}现在，让我们看看如何实现递归delete(...)方法，并从终止递归的两个基本条件开始:当前节点为空或列表中的单个节点，这也是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
}达到第一个基本条件意味着我们已经到达链表的末尾(无论是否找到key )，或者链表是空的。我们完成了，我们返回一个对链表的引用。
第二个基本条件检查我们的当前节点是否是头节点，以及它是否匹配key。在这种情况下，我们还检查它是否恰好是链表中的单个节点。在这种情况下，头节点需要“特殊”处理，并且必须被分配null才能被删除。当然，在删除head节点之后，列表是空的，我们就完成了，所以我们返回一个对链表的引用。
下一个条件检查当前节点是否与key匹配，如果它是头节点，但不是列表中的单独节点。
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仍然是前一个节点。
下一个案例涵盖了一个与key匹配的常规(中间或尾部)节点
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
}在这种情况下，我们通过将前一个节点的next指针从当前节点解除链接并将其分配给当前节点地址的下一个来删除当前节点。我们本质上“跳过”当前的节点，它变成了爬行。然后，我们使用前一个节点作为当前节点，并使用null作为前一个节点。
在所有这些已处理的案例中，我们都匹配了key。最后，我们处理没有匹配的情况：
private LinkedList delete(Node node, Node prev, int key) {
//...previous code here
return delete(node.next, node, key);
}显然，我们使用下一个节点作为当前节点，将旧的当前节点作为前一个节点。在所有递归调用中，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(...)方法以符合要求。我们可以保留对当前node和前一个节点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);
}要测试此递归方法，请执行以下操作：
我已经通过外观方法deleteAll(...)添加了一个简单的main测试驱动程序方法来测试delete(...)方法的实现
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 []虽然距离最初的帖子已经过去了3年，但我相信其他一些初学Java的程序员，如果不是OP的话，会发现这个解释很有用。
https://stackoverflow.com/questions/52459075
复制相似问题