• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursion and linked lists

 
mike fusc
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20494
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
mike fusc
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20494
54
Chrome Eclipse IDE Java Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic