Trying to create a removeLastElement using recursion

Question

I need to make a method that removes the last element of a LinkedList using recursion. This is what I have so far but it doesn't seem to be removing the node...when i call list.size() it is still the same size with the same values. What am I doing wrong here? This is for Java by the way

public void removeLastElement(Node curr){
 if (curr == null)
 return;
 else{
 if(curr.next == null)
 curr = null;
 else
 removeLastElement(curr.next);
 }
 }

• Juvanis: you are giving a node parameter to method, so it means you surely know that it is the last element, so why do you use a method and more interestingly "recursion" to remove the last element althoguh you already know which is the last element in your list?
• Ramandeep Singh: i think you have to traverse the node first...something like curr=curr.next before removeLastElement(curr.next); ..!!..and then change the last statement to : removeLastElement(curr);
• user1267952: my homework assignment asks that we use recursion. i guess we aren't supposed to use a node parameter then? judging from your response.

Answer 1

In a LinkedList to remove the last element you have to get the penultimate element and set

curr.next = null

• user1267952: how would i write that? i'm new to linked lists and recursion. sorry :(
• Luiggi Mendoza: @Ruuhkis add the "@" before the name so people could receive the comment in their inbox :)

Answer 2

You're in the right way to get the recurrent function to remove the last node. The problem is you're identifying the penultimate node with curr.next == null, if you got it, you nullify it, but that's your actual input! So, you must check if the actual node is the antepenultimate node on the list:

if (curr.next.next == null) {
 curr.next = null; //Now you're modifying the data in your input.
}

With this change, there are more basic cases to check, but that's up to you, my friend.

• mikek3332002: antepenultimate: I assume you mean 3rd last?
• Luiggi Mendoza: @mikek3332002 yes that's what I mean

Answer 3

Boolean deleteLast(Node n)
{
 if(n.next == null)
 return true;
 if(deleteLast(n.next))
 {
 n.next = null;
 return false;
 }
 return false;
 }

Answer 4

Node deleteLast(Node n) {
 if (n.next == null)
 return null;
 n.next = deleteLast(n.next);
 return this;
}

The general idea is you ask the next node "hey, can you tell me where you are, and delete your last node?" The last node can then just say "I'm nowhere" and it'll all fall into place.

This is very similar to Aadi's answer, just using Nodes instead of booleans.