How to remove every third element from a linked list recursively?

I would like to iterate over a linked list and remove every third element recursively.

If the end of the list is reached, I do the same call on those elements which are left in the linked list. I’m doing that until only one element is left in the linked list.

My solution which does not work as expected:

import java.util.LinkedList;
import java.util.List;

    public class test {

    public static void main(String[] args) {
        int randomNumber = (int )(Math.random() * 50 + 1);
        List<Integer> testList = new LinkedList<Integer>();

        for (int i = 1; i <= randomNumber; i++)
        {
            testList.add(i);
        }
    }
        public void removeElements(List testList)
        {
           for(int i = 0; i < testList.size();i++){
                if(i % 3 == 0){
                    testList.remove(i);
                }
            }
            if(testList.isEmpty()){
                return;
            }
            removeElements(testList-1);
        }
 }

Answer

If you’re doing it recursively, then there’s no need to iterate. Simplify the problem down to one iteration and apply it to the current state, and then the rest of the list. There doesn’t seem to be a node class, so it has to be done with indexes.

Removing the third element means keeping the current two elements and removing the one after them. We also have to take into account that the list will ‘shift’ when we remove one, so we don’t have to advance forward after removing. The next ‘current’ will be the same index as the index we removed from.

public void removeElements(List list, int current) {
   int removeIndex = current + 2;     // remove the third element
   if (removeIndex >= list.size())    // if there isn't one, stop
      return;

   list.remove(removeIndex);          // if there is one, remove it
   removeElements(list, removeIndex); // continue with the rest of the list
}

To avoid always having to prep the method, you can write a second one that does it for you:

public void removeElements(List list) {
   removeElements(list, 0);
}

Ex:

List<Integer> list = new LinkedList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);

removeElements(list);

for (int x = 0; x < list.size(); x++)
   System.out.println(list.get(x));

// output: 1 2 4 5 7 8 10

Since you updated which nth item you want to remove, this can easily be changed by modifying the value that is added to the current index:

public void removeElements(List list, int current, int n) {
   int removeIndex = current + n - 1;    // remove the nth element
   if (removeIndex >= list.size())       // if there isn't one, stop
      return;

   list.remove(removeIndex);             // if there is one, remove it
   removeElements(list, removeIndex, n); // continue with the rest of the list
}

public void removeEverySecond(List list) {
   removeElements(list, 0, 2);
}

public void removeEveryThird(List list) {
   removeElements(list, 0, 3);
}

// etc.

Answer

Leave a Reply Cancel reply