Удалите все вхождения элемента в связанном списке с помощью рекурсии - PullRequest
Новая
       71

Удалите все вхождения элемента в связанном списке с помощью рекурсии

0 голосов
/ 21 апреля 2019

Я делаю реализацию структуры данных Linked-List, и я жду возможности реализовать 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);
      }
    }
  }
}

Я понимаю проблему, я работаю с копиями списка, а не с оригиналом, поэтому, как я могу объединить или сделать этот саб в исходный список?

Ответы [ 2 ]

0 голосов
/ 21 апреля 2019

Я бы предложил сделать это в отдельной статической функции вместо того, чтобы делать это в реальном классе узлов, поскольку вы рекурсивно просматриваете весь связанный список. 

public void removeAllOccurences(Node<T> head, Node<T> prev, T elem) {
    if (head == null) {
      return;
    }
    if (head.value.equals(elem)) {
      Node<T> temp = head.next;
      if (prev  != null) {
        prev.next = temp;
      }
      head.next = null; // The GC will do the rest.
      removeAllOccurences(temp, prev, elem);
    } else {
      removeAllOccurences(head.next, head, elem);
    }
  }
0 голосов
/ 21 апреля 2019

Если бы у меня было , чтобы сделать это с рекурсией, я думаю, это выглядело бы примерно так: 

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;
    }
}
...