使用递归将数组转换为自定义 LinkedList 类

Question

我正在使用一个自定义 LinkedList 类，如下所示：

public class LinkedList {
    // Get and Set methods are NOT necessary!

    private LinkedList next;    
    private final String word;

    public LinkedList(String word, LinkedList next) {
        this.word = word;
        this.next = next;
    }

现在我的任务是编写一个方法，该方法采用字符串数组，并将每个字符串对象转换为不带循环的 LinkedList，因此使用递归。如何在没有循环的情况下完成此操作？这对我来说是难以想象的。我从哪里开始呢？

编辑：让我澄清一下，我应该编写的函数只接受一个参数，它是一个字符串数组，并返回一个 LinkedList..

Answer 1

enter code here
    public LinkedList arrayToLinkedList(String[] myArray)
{
        String[] toConvert = myArray;
        List<String> toConvertList = (List) Arrays.asList(toConvert);
        LinkedList<String> convertedLinkedList = new LinkedList<String>(toConvertList); 
        return convertedLinkedList;
}

Answer 2

可能只是我，但我不喜欢所提供的任何解决方案。

    /**
     * Creates linked list from array input.
     * 
     * @param input
     *            data array
     * @return linked list with data
     */
    public static LinkedList Of(String[] input) {
        // Checks if array has elements.
        if (input == null || input.length < 1)
            return null;
        // Starts creating the array using overload 2.
        return LinkedList.Of(input, 0);
    }

    /**
     * Creates linked list from array input (overload 2).
     * 
     * @param input
     *            data array
     * @param i
     *            counter to remember at what element is current
     * @return linked list with data
     */
    public static LinkedList Of(String[] input, int i) {
        //Tests if counter is within array elements. 
        if (input.length - 1 > i)
            // Returns new element with (current element data, reference
            // to next element). Note that next element will be returned
            // by this same method (this is why it is recursive).
            return new LinkedList(input[i], LinkedList.Of(input, i + 1));
        //Last element. From here backtracking will begin. 
        return new LinkedList(input[i], null);
    }

这是其他内容：

    public String toString() {
        StringBuilder sb = new StringBuilder(this.word);
        LinkedList tmp = this;
        while (tmp.next != null) {
            sb.append(" > ");
            tmp = tmp.next;
            if (tmp.word != null)
                sb.append(tmp.word);
        }
        return sb.toString();
    }

并进行测试：

    String str = "Neque porro quisquam est qui dolorem ipsum quia "
            + "dolor sit amet, consectetur, adipisci velit...";
    LinkedList ll = LinkedList.Of(str.split("\\s+"));
    System.out.println(ll);

Answer 3

我不确定您使用的是什么语言，但这里有一个总体想法：

public LinkedList myfunction(String arr[]) {
    if(arr.empty == true)
        return void;

    //return the array minus the first element
    String shorterarray[] = substr(arr[],1);

    //recursively create the next element
    LinkedList myItem = new LinkedList(arr[0], myfunction(shorterarray[]));
}

您必须使用您使用的任何语言进行减法和边界检查。

Answer 4

怎么样：

public static void main(String[] args) {
    String[] data = new String[] { "1", "2", "3" };

    LinkedList head = build(data);
    while (head != null) {
        System.out.println(head.word);
        head = head.next;
    }
}

private static LinkedList build(String[] data) {
    if (data == null || data.length == 0) {
        return null;
    }

    LinkedList head = new LinkedList(data[0], null);
    build(head, data, 1);
    return head;
}

private static LinkedList build(LinkedList node, String[] data, int index) {
    if (index == data.length) {
        return node;
    }

    node.next = build(new LinkedList(data[index], null), data, ++index);
    return node;
}

private static class LinkedList {
    private final String word;
    private LinkedList next;    

    public LinkedList(String word, LinkedList next) {
        this.word = word;
        this.next = next;
    }
}

补充一下，可能还值得指出的是，使用递归创建集合在实践中确实很糟糕 - 它很容易耗尽堆栈大小。

Answer 5

首先，任何你能用迭代（循环）做的事情都可以用递归来做，反之亦然（尽管没有尾部调用消除，这是Java所没有的，递归通常比迭代更昂贵）。

当试图弄清楚如何递归地解决问题时，您想要弄清楚如何分解问题的一个或多个看起来像同一类问题但只是更小的问题。对于列表问题，通常意味着当给定一个 n 元素列表时，您想要递归处理 n-1 个元素。您还需要有一个基本情况，以便递归终止。对于列表，基本情况通常是包含 0 个元素的列表。

数组很像列表，但 Java 数组没有切片（即：您不能只传递数组的一部分），因此您需要一个辅助方法来知道我们关心数组的哪一部分关于：

private static LinkedList fromArray(String[] a, int offset) {

由于您的 LinkedList 类分解为一个单词，然后是列表的尾部部分（由 next 指向），因此我们也处理尾部是有意义的输入数组的一部分。 offset 参数让我们知道我们将查看数组尾部的多少部分：这是我们关心的第一个索引。

public 方法只会调用 helper 方法，为其提供偏移量 0：

public static LinkedList fromArray(String[] a) {
    return fromArray(a, 0);
}

偏移量 0 意味着我们关心元素 0（第一个元素）及其后面的每个元素。

现在编写“helper”方法，这是完成所有实际工作的地方。

首先，摆脱基本情况。基本情况是我们要转换的数组部分为空。如果 offset >= a.length 就是这种情况。在这种情况下，我们希望返回一个空的 LinkedList，它实际上由 null 表示。因此在这种情况下返回 null。

一旦处理了基本情况，就考虑递归情况。我们关心的数组部分中有一个或多个元素。让我们创建一个 LinkedList 来保存第一个元素 a[offset]。 （即我们关心的第一个元素。回想一下，助手只关心从 offset 开始到末尾的数组部分。）其余元素可以通过调用我们自己来处理传入相同的数组，但将 offset 加一，因为我们不希望递归调用处理我们已经处理过的元素。

Answer 6

调用一个带有三个参数的函数；源数组、数组中的当前位置和目标链表。

这是否让你头脑清醒/你能从那里弄清楚吗？

Answer 7

试试这个：

private LinkedList formlist(LinkedList list, String[] str, int length, int i) {
    if(i==length)
        return list;
    return formlist(new LinkedList (str[i],list),str,length,i+1);

}

Answer 8

好的，因为需要使用 String[] 参数的单个方法。
这是一个java示例。 （基于之前的答案，但转换为java）

private LinkedList build(String arr[]) {
    if(arr.length == 0)
        return null;

    //return the array minus the first element
    String shorterarray[] = Arrays.copyOfRange(arr, 1, arr.length);

    //recursively create the next element
    return new LinkedList(arr[0], build(shorterarray));
}