如何递归连接字符串元素列表

Question

我正在查看准备考试的示例，坦率地说，我对递归或列表，但特别是列表不是很好。

给出了一个节点类，它将保存字符串（不是泛型的）编写一个名为concat的递归java函数，它接受一个代表链表头部的节点并返回一个表示链表中所有元素串联的字符串如果列表为空，则字符串应该也是。

任何帮助，将不胜感激。

（以下是我不得不类型之前，我问的问题:)

public static String FindConcat(Node head) { 
    String s = ""; 
    if(head == null) return s; 
    else if(head.next = null) { 
     s += head.data; 
     return s; 
    } 
    else { 

    } 

} 

感谢repsonses。

Answer 1

如果您的节点为空，则返回一个空字符串。

否则，获取字符串，进行递归调用（以获得其余节点的连接结果），并将其附加到字符串并返回结果。

Answer 2

因为这听起来像作业，我会提出建议。

首先写入如果列表只有一个元素（即没有下一个节点）将工作的方法。用它作为递归调用的基础。

Answer 3

对链表的递归遍历通常看起来像是看你是否在列表的末尾（你得到的引用是null），如果你不是，则对下一个元素进行递归调用的名单，如果你是，做基本案件的事情。假设节点像这样从外面：

public class Node{ 
    public Node getNext(); 
    public String toString(); 
} 

...你的方法是这样的（你正在使用运行该出的类中）：

public String concatList(Node head){ 
    if(head == null){ 
     return ""; //empty list is a null pointer: return empty string 
    } 
    return head.toString() + concatList(head.getNext()); 
} 

的结束该列表或根本没有列表看起来是相同的 - 一个空指针 - 并返回空字符串，如指定;其他一切都将当前节点连接到通过获取字符串的整个剩余部分的连接版本创建的列表。请注意：如果某个东西损坏了你的列表，所以它实际上是一个循环，它没有检查它，并且将永远运行直到它用完堆栈内存，除非Java正确地检测到这个递归函数的循环优化，并且它会只是永远运行。

Answer 4

在这种情况下，什么是递归找到基本情况，以及如何将数据“分开”到这个基本情况。所以首先定义你的“基本情况”。

• 基本情况：函数参数为空
• ，直到你得到的基本情况，追加节点的文本，并跳过的第一个元素

这是你的方法：

public static String FindConcat(Node head) { 
    if (head == null) 
     return ""; // base case 

    // devide it down (run recursive FindConcat on the _next_ node) 
    return head.data + FindConcat(head.next); 
} 

这个简单的例子将打印hello this is a linked list：

public class Test { 
    // this is a very basic Node class 
    static class Node { 
     String text; 
     Node next; 

     public Node(String text) { 
      this.text = text; 
     } 
     // used for building the list 
     public Node add(String text) { 
      next = new Node(text); 
      return next; 
     } 
    } 

    // this is the recursive method concat 
    public static String concat(Node node) { 
     if (node == null) 
      return ""; 

     return node.text + " " + concat(node.next); 
    } 

    public static void main(String[] args) { 
     // build the list 
     Node head = new Node("hello"); 
     head.add("this").add("is").add("a").add("linked").add("list"); 

     // print the result of concat 
     System.out.println(concat(head)); 
    } 
} 

Answer 5

这是一个非常完整的例子：

import java.util.Arrays; 
import java.util.List; 
import java.util.UUID; 

public class RecurisveLinkedListExample 
{ 
    public static String concat(final Node node) 
    { 
     if (node == null) 
     { 
      return ""; 
     } 
     else 
     { 
      return node.getData() + concat(node.getNext()); 
     } 
    } 

    public static void main(String[] args) 
    { 
     final List<String> input = Arrays.asList("A", "B", "C", "D"); 
     final Node head = new Node(null, input.get(0)); 
     Node previous = head; 
     for (int i = 1; i < input.size(); i++) 
     { 
      previous = previous.addNext(input.get(i)); 
     } 

     System.out.println(concat(head)); 
    } 

    public static class Node 
    { 
     private final UUID id; 
     private final Node previous; 
     private final String data; 
     private Node next; 

     public Node(final Node previous, final String data) 
     { 
      this.previous = previous; 
      this.data = data; 
      this.next = null; 
      this.id = UUID.randomUUID(); 
     } 

     public Node getPrevious() 
     { 
      return previous; 
     } 

     public String getData() 
     { 
      return data; 
     } 

     public Node addNext(final String data) 
     { 
      this.next = new Node(this, data); 
      return this.next; 
     } 

     public Node getNext() 
     { 
      return next; 
     } 

     @Override 
     public String toString() 
     { 
      return String.format("%s:%s:%s", 
        this.previous == null ? "HEAD" : this.previous.id, 
        this.data, 
        this.next == null ? "TAIL" : this.next.id); 
     } 
    } 
}