java - 使用递归删除链表中所有出现的元素

Question

我正在实现链接列表数据结构，并且希望使用递归实现所有出现的元素的 remove 方法，这是我的一段代码:

public class MyLinkedList<T> {
  private Node<T> head;
  private Node<T> last;
  private int length;

  public void remove(T elem) {
    if (!(this.isContained(elem)) || this.isEmpty())
      return;
    else {
      if (head.value.equals(elem)) {
        head = head.next;
        length--;
        remove(elem);
      } else {
        // This is a constructor which requieres a head and last, and a length
        new MyLinkedList<>(head.next, last, length-1).remove(elem);
      }
    }
  }
}

我确实理解这个问题，我正在使用列表的副本而不是原始列表，那么，我如何合并或将此子项添加到原始列表中？

Answer 1

如果我不得不使用递归来完成它，我认为它会看起来像这样:

public void remove(T elem)
{
    removeHelper(null, this.head, elem);
}

private void removeHelper(Node<T> prev, Node<T> head, T elem)
{
    if (head != null) {
        if (head.value.equals(elem)) {
            if (head == this.head) {
                this.head = head.next;
            } else {
                prev.next = head.next;
            }
            if (this.last == head) {
                this.last = prev;
            }
            --this.length;
        } else {
            prev = head;
        }
        removeHelper(prev, head.next, elem);
    }
}

郑重声明，如果我不需要必须使用递归，我会像这样线性地执行:

private void remove(T elem)
{
    Node<T> prev = null;
    Node<T> curr = this.head;
    while (curr != null) {
        if (curr.value.equals(elem)) {
            if (this.last == curr) {
                this.last = prev;
            }
            if (prev == null) {
                this.head = curr.next;
            } else {
                prev.next = curr.next;
            }
            --this.length;
        } else {
            prev = curr;
        }
        curr = curr.next;
    }
}