File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Recursion and linked lists Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


JavaRanch » Java Forums » Java » Java in General
Bookmark "Recursion and linked lists" Watch "Recursion and linked lists" New topic
Author

Recursion and linked lists

mike fusc
Greenhorn

Joined: Mar 07, 2010
Posts: 15
Hi,

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


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
Sheriff

Joined: Oct 27, 2005
Posts: 19697
    
  20

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):
You can shorten this code but this is how it basically works.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
mike fusc
Greenhorn

Joined: Mar 07, 2010
Posts: 15
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
Sheriff

Joined: Oct 27, 2005
Posts: 19697
    
  20

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursion and linked lists