CODEWITHSUNDEEP
javarecursionlinked-list
billybob2
billybob2

Reputation: 701

Linked List, Going through backwards recursively

I have a simple assignment to do that I cant seem to figure out. It this prebuild function I have to put this list into reverse order, using the skeleton function given to me (not allowed to change what it returns and what its parameters).

  //----------- helper function
/**
 * cursedReverse( DataNode )
 *     recursively chase list until get to the end.
 *     create new list at the end of the recursion, return
 *     add nodes to the returned list at the end of the list
 *        since you're coming back up, the end will be reversed.
 * @param node DataNode
 * @return DataList
 */
public static DataList cursedReverse( DataNode node )
{
    //////////////////////////////////////////////////////////////
    // 4. traverse "list", recursively
    //++++++++++++++++++++++++++

    /*
   while( node.next() != null ){
       System.out.println("Going down list recursively " + node.data().value );
       return cursedReverse( node.next() );
   }
    if( node.next() == null ){
        System.out.println("At end of the list " + node.data().value );
       // cursedReverse( node );
        //return temp
    }
    */
    DataList d1 = cursedReverse( node );
    if( node.next() == null ) {
        System.out.println(" We have Reached the end of the list ");
    } else if( node != null ){
        System.out.println("NOT NULL");

    }




   // DataList remaining = cursedReverse( node.next() );


    return null;
}

I know how to recursively get done to the botton of the list. But its a one way linked list, meaning I can only say node.next() to get the next list on the way down. So I can't think of a way to go backwards up the DataList.

Upvotes: 0

Views: 455

Answers (2)

ChiefTwoPencils
ChiefTwoPencils

Reputation: 13930

But its a one way linked list, meaning I can only say node.next() to get the next list on the way down. So I can't think of a way to go backwards up the DataList.

It doesn't need to be doubly-linked. Recursion will allow you to access it in reverse order as the stack unwinds.

As you make recursive calls you will go node-by-node (using next) down the list until you reach the last node (the end of the list).

Once you reach the end you will start adding nodes to the reversed list (now your last node becomes the first in that list).

After each call completes you will return to the previous call (the one you passed next from). That will be the location of the previous node. Add it to the list.

Continue to do so until you're back at the head.

I'm not a fan of checking for null (if(node != null) {...}) to take action (so-to-speak). I like to use a null node as the base case. So, mine would look something like this:

public static DataList cursedReverse( DataNode node ) {
    if (node == null) 
        return new DataList();
    DataList dl = cursedReverse(node.next());
    dl.add(node);
    return dl;
}

The first call should be cursedReverse(head);.

Upvotes: 3

OldCurmudgeon
OldCurmudgeon

Reputation: 65813

This:

DataList d1 = cursedReverse( node );

is clearly wrong. The first thing you do when entering cursedReverse is to call cursedReverse. That's a StackOverflow right there.

Recursion is a little like proof by induction. There are three main parts to it.

  1. Make sure there is a state where recursion will stop and unwind.
  2. Make sure recursion continues until stopped.
  3. Make sure that you achieve state 1 eventually.

You have broken rules 1 and 3.

You have broken rule 1, obviously.

You have broken rule 3 by not passing a different parameter to cursedReverse. Something like this might be a good direction to take.

DataList d1 = cursedReverse( node.next() );

To fix 1 you need to do something like:

    if (node != null) {
        if (node.next() != null) {
            DataList reversed = cursedReverse(node.next());
            ...
        } else {
            // Last in the list.
        }
    } else {
        // Null node! Hit the end.
    }

i.e. Make sure the method will do nothing (or something trivial) when you detect the end - do not recurse again.

Upvotes: 2

Related Questions