将字符串转换为链接列表并使用递归浏览它

Question

我对递归很陌生（我需要使用它），并且在使用我的一种搜索方法时遇到了一些严重的逻辑问题。请看下面：

//these are methods within a Linked List ADT with StringBuilder functionality
//the goal here is to access the char (the Node data) at a certain index
public char charAt(int index)
{
    if((firstNode == null) || (index < 0) || (index >= length + 1))
    //firstNode is the 1st Node in the Linked List, where the search begins
    {
        System.out.println("Invalid Index or FirstNode is null");
        IndexOutOfBoundsException e = new IndexOutOfBoundsException();
        throw e;
    }
    else
    {
        char c = searchForChar(firstNode, index);
        return c;
    }
}
private char searchForChar(Node nodeOne, int index)
{
    int i = 0;
    if(nodeOne == null) //basecase --> end
    {
        i = 0;
        System.out.println("nodeOne null, returning null Node data");
        return 'n';
    }
    else if(i == index) //basecase --> found
    {
        i = 0;
        return nodeOne.data; //nodeOne.data holds the char in the Node
    }
    else if(nodeOne != null) //search continues
    {
        searchForChar(nodeOne.next, index);
        i++;
        return nodeOne.data;
    }
    return nodeOne.data;
}

输出是"nodeOne null，返回 null 节点数据"的长度为 1 的打印。我不明白当最后一个 else-if 语句中的递归语句似乎也像第一个 if 语句中的空语句一样时，它是如何到达的。

我尝试重新排列 if 语句，以便if(nodeOne != null)排在第一位，但这给了我一个NullPointerException.不知道我做错了什么。特别是因为我可以使用toString()方法打印节点中的数据，因此我知道节点没有空数据。

谁能帮我理解？

Answer 1

我写了一个完整的例子，我希望这是你需要的。如果您使用i < 14循环字符串StackOverflow，它还将打印空字符如果您使用i < 15它会给您一个IndexOutOfBoundsException。每次您实际上说我需要将跃点(index - 1)到目标节点时，将索引减少 1。

public class CharTest {
    public static class Node {
        private char content;
        private Node nextNode;
        public Node () {
            content = '';
            nextNode = null;
        }
        public Node (String str) {
            Node temp = this;
            for (int i = 0; i < str.length(); i++) {
                temp.content = str.charAt(i);
                temp.nextNode = new Node();
                temp = temp.nextNode;
            }
        }
        public char charAt(int index) {
            if (index == 0) {
                return content;
            } else if (index < 0 || nextNode == null) {
                throw new IndexOutOfBoundsException();
            }
            return nextNode.charAt(index - 1);
        }
    }
    public static void main(String[] args) {
        Node test = new Node("StackOverflow");
        for (int i = 0; i < 13; i++) { 
            System.out.print(test.charAt(i));
        }
        System.out.println();
    } 
}

我将把迭代或递归地制作toString()方法留给读者练习。但是，由于性能原因，使用 StringBuilder 或 char[] 将是一个好主意。