java 如何递归连接字符串元素列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4371040/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to recursively concatenate a list of string elements
提问by Blake
I am looking at examples getting ready for an exam, and frankly, I am not very good with either recursion or lists, but particularly lists.
我正在查看准备考试的示例，坦率地说，我不太擅长递归或列表，尤其是列表。
A node class is given, it will hold strings (not generic) write a recursive java function called concat that takes a node representing the head of a linked list and returns a string representing the concatenation of all the elements of the list if the list is empty the string should be as well.
给定了一个节点类，它将保存字符串（非泛型）编写一个名为 concat 的递归 java 函数，该函数接受一个表示链表头部的节点，并返回一个表示列表中所有元素串联的字符串（如果列表是）空字符串也应该是。
Any help would be appreciated.
任何帮助，将不胜感激。
(The following is what I had type before I asked the question:)
（以下是我在提问之前输入的内容：）
public static String FindConcat(Node head) {
String s = "";
if(head == null) return s;
else if(head.next = null) {
s += head.data;
return s;
}
else {
}
}
Thanks for the repsonses.
感谢您的回复。
回答by dacwe
In this case what recursion is finding the base case and how to "devide" the data down to this base case. So first define your "base case".
在这种情况下，什么递归是找到基本情况以及如何将数据“分解”到这个基本情况。所以首先定义你的“基本情况”。
- Base case: argument to the function is null
- Till you get the the base case, append the text of the node and skip the first element
- 基本情况：函数的参数为空
- 直到获得基本情况，附加节点的文本并跳过第一个元素
This is your method:
这是你的方法：
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);
}
This simple example will print hello this is a linked list:
这个简单的例子将打印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));
}
}
回答by dacwe
Here is a very complete example:
这是一个非常完整的例子：
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);
}
}
}
回答by Karl Knechtel
If your node is null, return an empty string.
如果您的节点为空，则返回一个空字符串。
Otherwise, get the string, make a recursive call (to get the concatenated result for the rest of the nodes), and append that to the string and return the result.
否则，获取字符串，进行递归调用（获取其余节点的连接结果），并将其附加到字符串并返回结果。
回答by shsteimer
since this sounds like homework, i'll make a suggestion.
因为这听起来像是家庭作业，所以我会提出一个建议。
start by writing the method that will work if the list only has one element (ie there is no next node). use that as the basis for your recursive call.
首先编写如果列表只有一个元素（即没有下一个节点）将起作用的方法。将其用作递归调用的基础。
回答by Adam Norberg
Recursive traversal of a linked list generally looks like seeing if you're at the end of the list (the reference you got was null), and if you're not, doing something to a recursive call upon the next element of the list, and if you are, doing the base case thing. Assuming that nodes look like this from the outside:
链表的递归遍历通常看起来像查看您是否在列表的末尾（您得到的引用是null），如果不是，则对列表的下一个元素进行递归调用，并且如果你是，做基本情况的事情。假设节点从外面看起来像这样：
public class Node{
public Node getNext();
public String toString();
}
...your method looks like this (inside the class you're using to run this out of):
...你的方法看起来像这样（在你用来运行它的类中）：
public String concatList(Node head){
if(head == null){
return ""; //empty list is a null pointer: return empty string
}
return head.toString() + concatList(head.getNext());
}
The end of the list, or no list at all, looks the same- a null pointer- and returns the blank string, as specified; everything else takes the current node and concatenates it to the list created by getting the concatenated version of the entire remainder of the string.
列表的末尾，或者根本没有列表，看起来相同——一个空指针——并返回指定的空字符串；其他一切都采用当前节点并将其连接到通过获取字符串的整个其余部分的连接版本创建的列表。
Be careful: if something's corrupted your list so it's actually a loop, this has no checks for that and will run forever until it runs out of stack memory, unless Java correctly detects the loop optimization of this recursive function and it will simply run forever.
请注意：如果某些东西损坏了您的列表，因此它实际上是一个循环，则它不会对此进行检查，并且将永远运行直到堆栈内存用完为止，除非 Java 正确检测到此递归函数的循环优化并且它将永远运行。
