Recursion using Linked List Java

[Jony27]

Hi all, I am having a bit of trouble with a method to insert a char value in front of a specific char value using recursion.

Here's my recursive and wrapper methods

    /*
     * recursive method for inserting
     */
    public Csc2001Node insertBefore(char c, Csc2001Node head, char toInsert)
    {   
        if(head==null){
            return head = new Csc2001Node(toInsert);
        }        
        else if (head.next!=null && head.ch == c || head.ch == c) 
        {
            Csc2001Node nextNode = head.next;
            head.next = new Csc2001Node(toInsert);
            head.next.next = nextNode;
        }
         else
            head.next = insertBefore (c, head.next, toInsert);

         return head;
    }
    /*
     * wrapper method for inserting
     */
    public void insertBefore(char c, char toInsert){
        head = insertBefore(c, head, toInsert);
    }

This is a piece of code from my tester class which adds a character in front of a specific character.

		System.out.println("Trying to insert V before e into the front of the list and printing out the list");
		mylist.insertBefore('e', 'V');
		mylist.recursePrintList();

The output should be

Trying to insert Z before p, a character that does not exist in the list, and
printing out the list
V e a Y s t e r Z

But my method outputs

Trying to insert Z before p, a character that does not exist in the list, and printing out the list
eVaYsterZ

Notice how the V is outplace by one character.

Anyone shine a light on what Im doing wrong with my recursive method?

Thanks

 

[mid_gen]

Someone else on your course has already done this assignment thanks to stackoverflow...suggest you look there

 

[Jony27]

I have actually been spending half of the day looking through stackoverflow and google

Tried implementing a couple of the "solutions" but non have given me the right output for some reason

What I have is the closest I can get to the correct output.

 

[Nymins]

Good thing I choose CIT.

 

[djabs786]

should this block have a return statement?

else if (head.next!=null && head.ch == c || head.ch == c)
{
...
}

 

[Jjustme]

Isn't this:

head.next!=null && head.ch == c || head.ch == c

equivalent to this:

head.ch == c

Also, what I think you want to do is create a new node when that condition is true, and set the "next" pointer of that node to the current head.
Edit: Actually that would disconnect everything before the newly created node.

I think the problem is that you're creating a new node at head.next, when really head should be the next node from your newly created one.

Is the signature of the function fixed? I don't see how this would work, you'd need to know if the node you're visiting is the head, so you know to return a new head when you're adding to the beginning of the list, which is different behavior from inserting anywhere else on the list (where you don't need to return a new head).

 

[mid_gen]

I have actually been spending half of the day looking through stackoverflow and google

Tried implementing a couple of the "solutions" but non have given me the right output for some reason

What I have is the closest I can get to the correct output.

You know your university tutors are there for a reason and will help you with this stuff...but anyway, have you not looked at your classmates solution here?

http://stackoverflow.com/questions/...insert-before-method-cutting-off-rest-of-list