Member Avatar for modernage

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:

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 ?

  • 4 Contributors
  • 6 Replies
  • 447 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by modernage

Recommended Answers

All 6 Replies

Member Avatar for jwenting

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.

Member Avatar for Dark_Omen

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

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.

import java.util.*;

public class Stars {
	public Stars(int n){
		stars(n);
	}
	
	public void dump(int n){
		for(int i = 0; i < n; i++){
			System.out.print("*");
		}
		System.out.println();
	}
	
	public void stars(int n){
		if(n==0)dump(0);
		else{
			dump(n);
			stars(n - 1);
			dump(n);
		}
	}
	
	public static void main(String[] args){
		int number;
		Scanner scan = new Scanner(System.in);
		number = scan.nextInt();
		Stars stars = new Stars(number);
	}
}
Member Avatar for modernage

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.

Member Avatar for Dark_Omen

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.

import java.util.*;

public class Permutation {
	private Random rand = new Random();
	private String scrambledString = "";
	private String inputString;
	private int stringLength;
	
	public Permutation(String aString){
		inputString  = aString;
		stringLength = aString.length();
		//permutates the string
		permutate(inputString, stringLength);
	}
	
	/**
	 * permutate, is a recursive algorithm that permutates a string
	 * @param s string passed in
	 * @param n int of the length of the length of the string
	 */
	private void permutate(String s, int n){
		String tmpString;
		if(s.length() == 0){
			//Base Case: Do nothing, just here to stop the recursion
		}
		else{
			int randNum = rand.nextInt(n);
			tmpString = dropOne(s, randNum);
			permutate(tmpString, n - 1);
		}
	}
	
	/**
	 * dropOne, drops one of the letters from the string passed in
	 * @param s string 
	 * @param n length of s
	 * @return the remaining portion of the string after a letter has been taken out
	 */
	private String dropOne(String s, int n){
		String tmpString = "";
		for(int i = 0; i < s.length(); i++){
			if(i != n){
				tmpString = tmpString + s.charAt(i);
			}
		}
		scrambledString = scrambledString + s.charAt(n);
		return tmpString;
	}
	
	/**
	 * toString returns the scrambled string (Permutated string)
	 */
	public String toString(){
		return scrambledString;
	}
}
public class PermutationDriver {
	public static void main(String[] args) {
		Permutation perm1 = new Permutation("abcdefg");
		Permutation perm2 = new Permutation("abcdefg");
		Permutation perm3 = new Permutation("abcdefg");
		Permutation perm4 = new Permutation("abcdefg");
		Permutation perm5 = new Permutation("abcdefg");
		System.out.println(perm1);
		System.out.println(perm2);
		System.out.println(perm3);
		System.out.println(perm4);
		System.out.println(perm5);
	}
}
import java.util.*;

public class Set64 implements Iterator {
	Object[] array = new Object[64];
	final int MAX = 64;
	int counter = 0;
	int nextOpenPosition = 0;
	
	public boolean hasNext(){
		return counter < nextOpenPosition;
	}
	
	public Object next(){
		return (counter < MAX) ? array[counter++] : null;
	}
	
	public void reset(){
		counter = 0;
	}
	
	public void add(Object o){
		if(nextOpenPosition < MAX){
			array[nextOpenPosition++] = o;
		}
	}
	
	public void scramble () {
		   String s = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789$#";
		   s = s.substring(0,nextOpenPosition); // use only as many characters as we need
		   Permutation p = new Permutation(s);  // scramble the string s
		   Object [] arr = new Object[64];   // start a new array
		   for (int i=0; i < nextOpenPosition; i++)
		     arr[p.toString().indexOf(s.charAt(i))] = array[i]; // fill up the new array
		   array = arr;  // reset array
		   reset(); // reset the iterator (this is probably appropriate)
	}
	
	public void remove(){
		
	}
}
Member Avatar for eCharisma

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 (head.next == null)
        return Integer.toString(head.item);
    else
        return backwards(head.next) + "," + 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.

Member Avatar for modernage

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.