java - 如何递归地从链表中删除每三个元素？

Question

我想遍历链表并递归地删除每三个元素。

如果到达列表末尾，我对链表中剩余的元素执行相同的调用。我一直这样做，直到链表中只剩下一个元素。

我的解决方案没有按预期工作:

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 1

如果您递归执行此操作，则无需迭代。将问题简化为一次迭代并将其应用于当前状态，然后是列表的其余部分。好像没有节点类，只好用索引来做。

移除第三个元素意味着保留当前的两个元素并移除它们之后的一个。我们还必须考虑到当我们删除一个列表时列表将“移动”，因此我们不必在删除后向前推进。下一个“当前”索引将与我们从中删除的索引相同。

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
}

为了避免总是需要准备方法，您可以编写另一个为您准备的方法:

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

例如:

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

由于您更新了要删除的第 n 个项目，因此可以通过修改添加到当前索引的值轻松更改:

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.