How to recursively concatenate a list of string elements

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 rep开发者_如何学Pythonresenting 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.

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.

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:

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

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.

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.

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:

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.

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