I am learning programming strategies in c++ and am working on RECURSION. I want to do the following task using recursion: Delete all the nodes in a that match the parameter I pass it, the trick is I want to delete them all but the last occurrence in the linked list.

so if my linked list was:

6->4->6->5->6->7->NULL

and I called the function delallbutlast (6);

The linked list would be as followed after the function call:

4->5->6->7->NULL

What would the pseudo. code be for this? I still trying to figure how recursive algoriths work especially one like this. Please help.There is no reason to USE a recursive algorithm here. An iterative one works just as well.


Of course seeing as your "dellallbutlast" definition, which one might logically conclude to delete all items but the last non-null entry (7) is instead deleting the first and third item of which the only COMMON attribute is the fact they are 6, which might make for a sensible definition (if an oddly named one) if it was not for another 6 element being left, again, for seemingly no reason. This makes it a tad difficult to even know what the point of said function is...

EDIT: oh wait, I see what it does, HEH didn't notice it had an argument. going to look over it.



First: it still doesn't make a whole lot of sense to use a recursive algorithm; an iterative one works just as well.
1. define a variable that holds a pointer to a linkedlist node; referred to as ltemp here.
2. Iterate through the list. With each node:
if the value matches our given parameter:
remove the node pointed to by ltemp, if ltemp!=null; (this is done by setting ltemp.prev.next to ltemp.next and ltemp.next.prev to ltemp.prev, and then deleting ltemp)
assign the value to ltemp.
3. (end of loop).


This would work since it only deletes the previous item it found when it finds a new one; no item will be found after the last one so it will not be deleted or removed.