在链表的某个索引处递归添加节点

Question

我正在尝试递归地在指定索引处添加列表节点。我的意思是，List类addAtRec（）调用ListNode类中的addAtRec（），该方法应该是递归的。

这就是我所做的：

列表：

public class List implements Cloneable {
private ListNode firstNode;
private ListNode lastNode;
private String name;
private int counter;
public List(){
    this("list");
}
public void addAtRec(Object obj, int k)
{
    if(firstNode != null)
        firstNode.addAtRec(obj, k, firstNode);
}
}

这当然只是相关的部分。。。

ListNode:

public class ListNode implements Cloneable {
Object data;
ListNode nextNode;
public ListNode(Object o){
    this(o,null);
}
public ListNode(Object o,ListNode node){
    data=o;
    nextNode=node;
}
public void addAtRec(Object obj, int k, ListNode current) throws ListIndexOutOfBoundsException {
    if(current.nextNode == null && k != 0)
        throw new ListIndexOutOfBoundsException(); //line 47
    if(k == 0)
    {
        ListNode l = new ListNode(obj);
        l.nextNode = current.nextNode;
        current.nextNode = l;
    }
    current = current.nextNode;
    addAtRec(obj, k, current); //line 55
    k--;
}

ListIndexOutOfBoundsException：

public class ListIndexOutOfBoundsException extends RuntimeException {
}

my main（）方法：

String s1 = "Objects";
    String s2 = "to";
    String s3 = "check";
    String s4 = "are";
    String s5 = "strings";
    List list = new List("My list");
    list.insertAtBack(s1);
    list.insertAtBack(s2);
    list.insertAtBack(s3);
    list.insertAtBack(s4);
    list.insertAtBack(s5);
    list.addAtRec(s3, 2);

错误：

Exception in thread "main" ListIndexOutOfBoundsException
at ListNode.addAtRec(ListNode.java:47)
at ListNode.addAtRec(ListNode.java:55)
at ListNode.addAtRec(ListNode.java:55)
at ListNode.addAtRec(ListNode.java:55)
at ListNode.addAtRec(ListNode.java:55)
at List.addAtRec(List.java:158)

我做错了什么？感谢您的时间和回答。

Answer 1

递归方法中有两个错误：

1. 在调用addAtRec(obj, k, current);之前，您应该将k减少1，因此最好在此行之前调用k--。

2. 一旦达到基本情况（当k == 0时）并执行添加新节点的逻辑，递归方法就必须停止，可能只需要一个简单的return;语句。在这种情况下，你不会停止它，所以你每次都会打电话给它，直到到达列表的末尾。

基于这两条建议，您的代码应该如下所示：

public void addAtRec(Object obj, int k, ListNode current)
    throws ListIndexOutOfBoundsException {
    //always use braces even for single line block of code
    if(current.nextNode == null && k != 0) {
        throw new ListIndexOutOfBoundsException();
    }
    if(k == 0) {
        ListNode l = new ListNode(obj);
        l.nextNode = current.nextNode;
        current.nextNode = l;
        //stopping the recursion
        return;
    }
    current = current.nextNode;
    //decrease k by 1 before calling your method recursively
    k--;
    addAtRec(obj, k, current);
}

这不是主要问题的一部分，但IMO您在列表中添加节点的方法应该属于List类，而不是ListNode。请记住，保存节点并决定如何绑定它们的数据结构将是List，而不是节点本身。