java - 在Java中递归删除节点链表
问题描述
我正在学习数据结构并尝试理解 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}
我真的很感激任何改进我的代码的提示。
解决方案
理解您的代码非常困难,但是当您要求逻辑以提高您的理解时,因此共享伪代码,您可以参考相应地更正您的代码。
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
推荐阅读
- php - PHP - 检查数组中的用户角色失败
- javascript - 如何确保所有 Jest 测试至少有一个期望?
- android - 使用 Linking.sendIntent() 打开设置
- docker - 如何使 Kubernetes 只读
- r - 如何将字符串作为变量传递给 felm 回归
- javascript - 由异步创建的未定义未解决?
- c# - 如何使用 C# 将 Excel 中的单元格设置为特定的日期格式?
- python - 使用正则表达式从行迭代中获取信息并将数据存储在嵌套字典中
- python - 存储 3D 数据以在 Python 中搜索的最佳方式
- r - 如何将for循环的结果存储到数据框中