Java

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

Please support our Java advertiser: Programming Forums - DaniWeb Sister Site

Thread Solved

•

Join Date: Apr 2006

Posts: 3

Reputation: modernage is an unknown quantity at this point

Solved Threads: 0

modernage

Offline

Newbie Poster

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

Apr 17th, 2006

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
OneListRec.backwards(head)

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:

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
     public static String backwards(IntNode head)
{
 
                                if (head == null) {
			return null;
		}
 
		if (head.next == null) {
			return head;
		}
 
		reverse(head.next);
		head.next.next = head;
		head.next = null;
		return head;
}
     public static String backwards(IntNode head)
{
                                
                                if (head == null) {
			return null;
		}

		if (head.next == null) {
			return head;
		}

		reverse(head.next);
		head.next.next = head;
		head.next = null;
		return head;
}

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

•

Join Date: Nov 2004

Posts: 6,143

Reputation: jwenting is just really nice

Solved Threads: 213

jwenting

Offline

duckman

Re: how do you reverse a linked list using recursion and return it as a string?

Apr 17th, 2006

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.

As people are clearly allowed to attack me but I'm not allowed to defend myself, I no longer post to this site.

•

Join Date: Apr 2004

Posts: 573

Reputation: Dark_Omen is an unknown quantity at this point

Solved Threads: 5

Dark_Omen

Offline

Posting Pro

Re: how do you reverse a linked list using recursion and return it as a string?

Apr 17th, 2006

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

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
String head = "47 23 2 5 98";
String returnHead = "";
StringTokenizer s = new StringTokenizer(head, " ");
while(s.hasNextToken()){
	 returnHead = s.nextToken() + ", " + returnHead;
}
String head = "47 23 2 5 98";
String returnHead = "";
StringTokenizer s = new StringTokenizer(head, " ");
while(s.hasNextToken()){
	 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.

Attached Files

Stars.java (493 Bytes, 15 views)

•

Join Date: Apr 2006

Posts: 3

Reputation: modernage is an unknown quantity at this point

Solved Threads: 0

modernage

Offline

Newbie Poster

Re: how do you reverse a linked list using recursion and return it as a string?

Apr 17th, 2006

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.

•

Join Date: Apr 2004

Posts: 573

Reputation: Dark_Omen is an unknown quantity at this point

Solved Threads: 5

Dark_Omen

Offline

Posting Pro

Re: how do you reverse a linked list using recursion and return it as a string?

Apr 17th, 2006

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.

Attached Files

	Permutation.java (1.4 KB, 25 views)
	PermutationDriver.java (489 Bytes, 7 views)
	Set64.java (1.1 KB, 11 views)

•

Join Date: Apr 2006

Posts: 8

Reputation: eCharisma is an unknown quantity at this point

Solved Threads: 1

eCharisma

Offline

Newbie Poster

Re: how do you reverse a linked list using recursion and return it as a string?

Apr 17th, 2006

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.

 Help with Code Tags 
 Java Syntax (Toggle Plain Text) 
public static String backwards(IntNode head)
    {
    if (head == null)
        return null;
 
    if (head.next == null)
        return Integer.toString(head.item);
    else
        return backwards(head.next) + "," + Integer.toString(head.item);
    }
public static String backwards(IntNode head)
    {
    if (head == null)
        return null;

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