How do you reverse a linked list using recursion, and return it as a string?

String backwards(IntNode head): Create and return a string containing the values in the input list, separated by commas, in reverse order. The last number should not be followed by a comma. Spacing within the string is not important. For example, if head points to the list: 12 45 -3 10 99 -47, the expression

should return the string "-47, 99, 10, -3, 45, 12".

i am confused as to how to do this. I tried to reverse the list recursively:

public static String backwards(IntNode head)
                                if (head == null) {
			return null;

		if ( == null) {
			return head;

		reverse(; = head; = null;
		return head;

i know this is wrong but i tried, but how do you return it as a string ?

Recommended Answers

All 6 Replies

Short answer: you don't.
Way too complex to achieve what you can do far more easily with just 2 commands.
Which those are I leave to you, the API documentation is your friend.

You want to use a StringTokenizer. So and them together.

String head = "47 23 2 5 98";
String returnHead = "";
StringTokenizer s = new StringTokenizer(head, " ");
	 returnHead = s.nextToken() + ", " + returnHead;

I think that is what you want.

jwenting is right you dont use recursion for this problem. When your thinking about a recursive problem you need to think is there a base case where this can end and a recursive case, which is the case that goes over and over until it reaches the base case. I attached a recursive class to this post so you can see how recursive methods work, if you're interested.

Oh, but I am being forced to use recursion for my homework assignment and I probably can't use StringTokenizer, they want us to learn how to implement the method ourselves. And the numbers in the list will be random numbers, not just those particular ones I wrote in. Yeah this sucks.

Ok, yeah, so it is kind of like a permutation of the numbers.
So, think of the base case and recursive case. So the base case is when there is 1 value left, and the recursive case takes out one of the numbers.
I added some files, this is a permutation of a string, but it is very similar to what your doing. But if the way i am thinking of it, you still might need stringtokenizer.

Returning the reversed list as a string is even easier than actually changing the links. When you get to the end of the list, return the value as a string. On the way back, append a comma and the value of the current node as a string to the return value of backwards.

public static String backwards(IntNode head)
    if (head == null)
        return null;

    if ( == null)
        return Integer.toString(head.item);
        return backwards( + "," + Integer.toString(head.item);

The trick to recursion is to let yourself go. :) If you think too hard about how it works or whether it's correct, you'll end up with a much more complicated solution than you need.

Thank you so much, it works!! yeah i thought about it way too much and I just got even more confused..but thanks again

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.