Recursion and linked lists

[mike fusc]

Hi,

I have to remove values from a linked list using recursion, no loops at all. So far I have this

 public static IntNode removeAll(IntNode head, int value){
		IntNode ptr;
		ptr = head;
		int i = ptr.data;
		if (i == value){
			if (ptr.next != null){
				ptr.data = ptr.next.data;
				ptr = ptr.next;
			}
			else {
				ptr = null;
			}
		}
		System.out.println(ptr.data);
		if (ptr.next!=null && ptr != null){
			ptr = ptr.next;
			removeAll(ptr, value);
		}
		return head;	
	}

I remove the value with no problem but the answer is returned with two consecutive values.

for example if i have 1 2 3 4 5 and i want to remove 3 the answer i get is 1 2 4 4 5.

Any help is appreciated thanks.

[Rob Spoor]

There are a few mistakes in your code. The most obvious is the return of "head". If head.data == value then you should not return head but the first available node with a different value. If I recall correctly that would be the return value of removeAll(head.next, value).

Let's consider the different cases:
1) head == null. There is nothing to check so return head (or null, but these are the same).

2) head.data == value and head.next == null. head should be removed, but it's the only node. The only thing to return is null.

3) head.data == value and head.next != null. head should be removed, the remainder should be checked. I'm sure you'll be able to figure out what to return.

4) head.data != value and head.next == null. head should not be removed and it's the only node. The only thing to return is head itself.

5) head.data != value and head.next != null. head should not be removed, but its next node may be. I'm sure you'll be able to figure out what to return.

In code (with gaps):

public static IntNode removeAll(IntNode head, int value)
{
    IntNode ptr = head;
    if (ptr != null)
    {
        if (ptr.data == value)
        {
            if (ptr.next == null)
            {
                ptr = null;
            }
            else
            {
                ptr = ???
            }
        }
        else
        {
            if (ptr.next != null)
            {
                ???
            }
            // else no need to do anything else
        }
    }
    // else return ptr itself
    return ptr;
}

You can shorten this code but this is how it basically works.

[mike fusc]

Thanks for the help.

I still can't get the list to shorten its length though. It will replace the value but it won't skip to the next number.

For example if i want to remove 5 and i insert 6 5 7 5 8 it will return 6 7 7 8 8

EDIT: never mind I figured it out. I was setting ptr = ptr.next when i should have been setting ptr.next = ptr.next.next.

Thank your for your help

[Rob Spoor]

What's your new code? Something tells me that the problem is the line "ptr.data = ptr.next.data;". That copies the data of the next node to this node but doesn't remove either node.