11 Replies - 387 Views - Last Post: 26 June 2019 - 11:51 PM Rate Topic: -----

#1 jstanley6   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 54
  • Joined: 22-January 17

Recursion reversing a LinkedList

Posted 24 June 2019 - 01:03 PM

Hello, I am trying to figure out how to reverse a LinkedList using recursion, here is the directions for it and a stubbed out version of it.
Part 1 - LinkedList: Write the subListReverse(fromIndex, toIndex) method for
LinkedListC.java. This method should print the contents of the list fromIndex toIndex (inclusive) in
REVERSE order. You may iterate to the fromIndex then you must utilize recursion to find the toIndex.
You are expected to write a private helper method to aid your recursion: that method has been stubbed
out for you. Follow the comments at the top of the LinkedListC file to aid you in accomplishing this
task. Do NOT attempt to modify Tester.java. Do NOT delete any of the .class files from the folder.
Check the output file (output.txt) to see what is produced from running the driver.
public class LinkedListC extends LinkedList
{
   // If the list is empty, print the message "The list is empty"
	// Check the indexes to ensure
	// -fromIndex is not less than 0
	// -toIndex is not greater than size
	// -fromIndex is less than toIndex
	// throw an IndexOutOfBoundsException if one of the indexes are incorrect
	// otherwise print the nodes fromIndex to toIndex in reverse order
  	public void subListReverse(int fromIndex, int toIndex)
	{
         
        }
}


Here is a bunch of code that I have tried but I just can't get the logic of this using recursion I can add loops in there to get to the lastIndex or the toIndex I think but recursion isn't supposed to use loops, so I am stuck and confused, this was supposed to be a fun project but has turned into a nightmare. The LinkedList is a custom Singly linked list with a dummy head node. Here is some code I have tried
	public void subListReverse(int fromIndex, int toIndex)
	{
  		//int cur = (int) this.head.data;
  		toIndex = this.size;
  		Node cur = this.head.next; 
  		if(this.size == 0) 
  			System.out.println("The list is empty.");
  		if(fromIndex < 0 || toIndex > this.size) 
  			throw new IndexOutOfBoundsException();
  		//this.head.next  = subListReverse(this.head.next, this.head.next.next);
  	  System.out.print(subListReverse(this.head.next, String.valueOf(toIndex)));
  		
	}// end subListReverse
  	
  	private String subListReverse(Node thisNode, String result) {

		if(thisNode != null) {
			result += subListReverse(thisNode.next, result);
		}

		return result;
	}
//  	
//  	 private Node subListReverse(Node first, Node second) {
//
//         Node newHeadR;
//         if(second == null)
//             return first;
//         else {
//             newHeadR = subListReverse(second, second.next);
//             second.next = first;
//             first.next = null;
//         }
//         return newHeadR; //change this line of code as needed.
    // }
//	  	public static String subListReverse(String str, Node cur, int start, int end) {
//	  		
//	  		if(cur.data.compareTo(start) <= 0 && cur.data.compareTo(end) >= 0  ) {
//	  			return str.charAt((int) cur.data) + subListReverse(str, cur.next, start, end);
//	  		}else if(str.length() == (int)cur.data)  {
//	  			return "";
//	  		}
//	  		else {
//	  			return subListReverse(str, cur.next, start, end);
//	  		}
//	  	}


Let me know if you need the LinkedList class attached to here, it isn't too long but it will take up a good amount of space and I can probably attach it as a file, or if all this seems long I can attach a couple java files to it that will be enough to try and run it and check it out.

Is This A Good Question/Topic? 0
  • +

Replies To: Recursion reversing a LinkedList

#2 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11604
  • View blog
  • Posts: 19,726
  • Joined: 19-March 11

Re: Recursion reversing a LinkedList

Posted 24 June 2019 - 01:11 PM

Feel free to post the LinkedList code if you want, it's best to just post it in [code] tags.

It might be a good idea at this point to step back from the code for a moment and describe, in English, how you're trying to solve the problem.
Was This Post Helpful? 0
  • +
  • -

#3 jstanley6   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 54
  • Joined: 22-January 17

Re: Recursion reversing a LinkedList

Posted 24 June 2019 - 01:24 PM

Ok here is the LinkedList class that is the parent class
public class LinkedList
{
   protected static class Node
   {
      protected Comparable data;
      protected Node next;
		
		protected Node ( Comparable data )
      {
         this.data = data;
         this.next = null;
      }// end constructor


    	protected Node ( Comparable data, Node next )
      {
         this.data = data;
         this.next = next;
      }// end constructor
     		
   }// end Node class

   
   protected Node head;
   protected int  size;
	
	// NOTE:  DUMMY header node.
	public LinkedList()
	{
		this.head = new Node(null);//set up DUMMY
		this.size = 0;
	
	}//end constructor

   // Return the present size of the linked list
   public int size()
   {  
		return size;
	}// end size
	
	/*********************************************************/
	/******** Your Code Goes Below Here **********************/
	/*********************************************************/

   // Empty out the linked list
	public void clear() {
		this.head.next = null;
		this.size = 0;
	}
	
	
	
		
	// Appends the specified elements to the end of this list.
	// Returns true if this collection changed as a result of the call.
		
	public boolean addAll(Integer[] c) {
		
		if(c == null) 
			throw new IllegalArgumentException("c passed in was null.");
		if(c.length > 0) {
            for (Comparable data : c) {
                addLast(data);
            }
            return true;
        }else {
            return false;
        }
	}
	
    public void addLast(Comparable data) {
	    if(data == null) {
	        throw new IllegalArgumentException("Data is null.");
        }

	    Node newNode = new Node(data, null);
	    if(this.head.next == null) {
	        this.head.next = newNode;
        } else {
	        Node cur = this.head.next;
	        while (cur.next != null) {
	            cur = cur.next;
            }
	        cur.next = newNode;
        }
	    this.size++;

    }
	
	
	// Write the toString method.
	// This method returns a string formatted
	// as follows: [first value, second value, ..., last value ]
	// Note that the last value does not have a comma after it.
	// Note also that there is a space after each comma.
	// The method should return 'List is Empty'
	// if the list is empty	
		
	  @Override
	    public String toString()
	    {
	        if(this.size == 0) {
	            return "List is empty";
	        }

	        String result = "";
	        if(head.next != null)
	        	result+= "[";
	        for (Node cur = this.head.next; cur != null; cur = cur.next) {
	            result += cur.data;
	            if(cur.next != null){
	                result += ", ";
	            }else {
	            	result += "]";
	            }
	        }
	        return result;

	    }//end toString
 }// end LinkedList class



What I think I need to do is I need a pointer that points the fromIndex to the node.data and I need to point the toIndex at the index of the list so that if I did list.size that would be the toIndex if the linked list was size 3 it would be index 2, just not interpreting it very well in code or maybe my thinking of it is off.
Was This Post Helpful? 0
  • +
  • -

#4 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11604
  • View blog
  • Posts: 19,726
  • Joined: 19-March 11

Re: Recursion reversing a LinkedList

Posted 24 June 2019 - 01:52 PM

So in a recursive function, you don't want to be thinking about that much stuff
Start with the easy thing: What's your base case? What do you return when you hit the base case?
Was This Post Helpful? 0
  • +
  • -

#5 jstanley6   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 54
  • Joined: 22-January 17

Re: Recursion reversing a LinkedList

Posted 24 June 2019 - 02:13 PM

Not sure of the base case yet, I do know that the fromIndex and toIndex has to be inbounds, and I would have to return the method call with the fromIndex and toIndex passed in the parameters
Was This Post Helpful? 0
  • +
  • -

#6 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11604
  • View blog
  • Posts: 19,726
  • Joined: 19-March 11

Re: Recursion reversing a LinkedList

Posted 24 June 2019 - 07:37 PM

Let's make it simpler for the moment. Forget about fromIndex and toIndex and just reverse the entire list.

What's the base case?

For concreteness, let's say the list we're working with is this one: A->B->C->D->NULL
A is the head, and D's next is a null pointer.
(but this doesn't matter at all to your statement of the base case, which should obviously not include any reference to A, B, C, or D)
Was This Post Helpful? 0
  • +
  • -

#7 jstanley6   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 54
  • Joined: 22-January 17

Re: Recursion reversing a LinkedList

Posted 24 June 2019 - 07:47 PM

Ok in this case I would say that
if(node.next == null){
//do recursive call
but not too sure because a null value would be entered into the list, but it needs to start reversing values when it gets to the last node, right?
Was This Post Helpful? 0
  • +
  • -

#8 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11604
  • View blog
  • Posts: 19,726
  • Joined: 19-March 11

Re: Recursion reversing a LinkedList

Posted 24 June 2019 - 09:07 PM

Let's keep it in English until we're sure we understand it. If you can spell it out in plain English, you're mostly there - don't get distracted by code until you know exactly what to write.

So you're saying the base case is "the next node is null". That's correct. But we're not going to do a recursion step here, because the base case means that we've recursed as far as we can go. Once we've hit the null, there's no more list, so we have to return something for the recursion step to work with.
If you want, we can put off the question of exactly what to return for the moment, it might become more obvious once we look at the recursion step.

So let's look at the recursion step. If the next node is not null what are we going to do?
This might be a good moment to introduce a more effective terminology. Let's consider the list as consisting of a HEAD (the first item in the list) and a TAIL (the rest of the list), and we can write the list as a whole as HEAD::TAIL. This will focus your attention on two of the three entities that you're allowed to think about in this step. The third entity you're allowed to think about, of course, is the function we're defining, which we'll need to call in the recursion step.

So:
to reverse a list, HEAD::TAIL,
if TAIL is NULL, return [SOMETHING TO BE DETERMINED]
else, return ___FILL IN THIS BLANK__
Was This Post Helpful? 0
  • +
  • -

#9 jstanley6   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 54
  • Joined: 22-January 17

Re: Recursion reversing a LinkedList

Posted 26 June 2019 - 04:34 PM

Ohh that makes sense, so if tail is null then we want to call the recursive function and have it reverse the nodes in the list, right? and if tail is not null it will just return the node that it is currently on? (don't think that is right..maybe increment the node, cur = cur.next?)

This post has been edited by jstanley6: 26 June 2019 - 05:10 PM

Was This Post Helpful? 0
  • +
  • -

#10 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11604
  • View blog
  • Posts: 19,726
  • Joined: 19-March 11

Re: Recursion reversing a LinkedList

Posted 26 June 2019 - 09:00 PM

Quote

if tail is null then we want to call the recursive function and have it reverse the nodes in the list,


If the tail is null then we have a list of just the head. That is we have the list A -> NULL

In that case, we want to return just the head. The reverse of a list of one element is just that element.

Quote

if tail is not null it will just return the node that it is currently on?


If the tail is not null, then there's more to do there, yes? We have to reverse the whole list.

Might be good to think about this with a couple of simple cases.

What is the reverse of an empty list?
What is the reverse of a list consisting of one element, A?
What is the reverse of a list consisting of two elements, A->B?
What is the reverse of a list consisting of three elements, A->B->C?
And the key question:
How can you describe the reverse of A->B->C in terms of the head, A, and the tail B->C, and the function reverse?
Was This Post Helpful? 0
  • +
  • -

#11 jstanley6   User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • Posts: 54
  • Joined: 22-January 17

Re: Recursion reversing a LinkedList

Posted 26 June 2019 - 09:34 PM

Ok, the reverse of an empty list is just an empty list, the reverse of a list containing only one element is just that element, A. The reverse of two elements A->B would be the head and tail nodes in the opposite positions which would be B->A, the head becomes head.next and the head.next becomes head. The reverse list of 3 elements A->B->C becomes C->B->A, again the last node switches with the head node so that C gets head position, and the second element would get the new head.next position, so to describe the head in terms of A->B->C, the head becomes the last node of the tail and the function reverse is switching each node and it's pointers around. Was this what you were asking or am I missing a concept? Recursion was always hard for me and never really understood it, but this is helping a lot, and sorry if I am taking up a lot of your time.
Was This Post Helpful? 0
  • +
  • -

#12 jon.kiparsky   User is offline

  • Beginner
  • member icon


Reputation: 11604
  • View blog
  • Posts: 19,726
  • Joined: 19-March 11

Re: Recursion reversing a LinkedList

Posted 26 June 2019 - 11:51 PM

You're mostly there. The key notion, and the one that I think will maybe unlock the concept for you, is to describe the reverse of H:T as reverse(T):H.

So if I have a list L consisting of a head H pointing to some list T, then whatever the reverse of T might be, if I attach H to the end of it, then I'll have the reverse of L.
And since T is a list, it consists of a head pointing to a tail, so I can play the same trick again, as many times as I need to ....

....

until I come to a list L which consists of a head H which points to no tail at all. In that case, I think we agree that the reverse of L is L itself, so I can return that.

And I can then use that return value as a list to which I append the head that I had in the previous step, and return the result...

...

until I unroll the stack of recursive calls and return the reverse of the original list.

Symbolically, if we let -> mean "produces" and :: mean "glommed on to", we can see this work in a simple example.

reverse (A::B::C:: D ) -> reverse(B::C:: D )::A 

reverse (B::C:: D ) -> reverse(C:: D )::B

reverse (C:: D ) -> reverse(D)::C

reverse (D) -> D    ---- since there is no call to reverse, we must be at the base case




Start by working your way down the list, and see how we simplify the argument to the reverse function at each step, until we get to the base case.

Then, to produce the final result, follow up from the base case, substituting in the production from each line into the right-hand side of the line above. reverse D is just D, so reverse(C:: D ) is D::C. reverse(B::C:: D ) is reverse(C:: D )::B, so that's D::C::B, and one more step takes you to a result which I think nobody can really argue with: reverse(A::B::C:: D ) is D::C::B::A
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1