How to recursively merge a list of string elements

Question

I look at examples that are ready for the exam, and to be honest, I'm not very good at recursion or lists, but especially lists.

The node class is specified, it will contain strings (not shared) that write a recursive java function called concat, which takes a node representing the head of the linked list, and returns a string representing the concatenation of all list items, if the list is empty, the string should also be .

Any help would be appreciated.

(I asked the following 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 repsons.

Answer 1

In this case, recursion finds the base case and how to "divide" the data into this base case. Therefore, first determine your "base case".

• Base case: function argument is null
• Until you get a basic example, add the text 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 prints 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 2

If your node is null, return an empty string.

Otherwise, get the string, make a recursive call (to get a concatenated result for the remaining nodes) and add it to the string and return the result.

Answer 3

since it sounds like homework, I will make an offer.

start by writing a method that will work if there is only one element in the list (i.e. the next node). use this as the basis for your recursive call.

Answer 4

A recursive traversal of a linked list usually looks like a look, if you are at the end of the list (you have a null link), and if not, then do something with a recursive call to the next list item, and if you do, do the basic case. Assuming the nodes look like this from the outside:

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

... your method looks like this (inside the class that you use to run it):

 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 an empty string, as indicated; everything else takes the current node and combines it into a list created by getting a concatenated version of the rest of the string.

Be careful: if something messes up your list, so this is actually a loop, there are no checks for this and it will work forever until the stack memory runs out, unless Java detects loop optimization of this recursive function, and just will run forever.

Answer 5

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); } } }