java - 递归地从链表中删除节点

Question

给定链表的头和要搜索的 int 作为参数，我需要一个方法来删除列表中第一次出现的该数字，并返回修改后的列表。但是我无法修改原始列表。我知道如何从列表中删除节点，但我不确定如何保持原始列表完整，因为这必须递归完成。下面是方法** 最初的 M 是原始列表。不知道再次调用该方法后还会是同一个列表吗...？

MyList removeNumber(MyList m, int removee){

Answer 1

这个想法是，最终的结构将是一个“Y”:一个双头列表(实际上是一个简单的图)。

Y 的一个分支是原始列表。另一个是删除节点的新列表。 Y 的垂直轴是您删除的元素后面的轴。这对于两个列表来说都是共同的。这是一些将 Y 翻转过来的 ASCII 艺术图，显示了 1 到 5 的列表，其中 3 被删除。

     new -> 1 -> 2 ------\
                          v
original -> 1 -> 2 -> 3 -> 4 -> 5 -> null

递归思考就是根据问题本身的较小版本加上固定的工作量来定义问题。您需要一个基本案例(或者可能几个)。

链表本身就是一个递归结构:

A list is either empty or it's an element linked by its "next" reference to a list.

请注意，这使用较小的列表定义了一个列表。基本情况是空列表。固定位是元素。

阅读这个定义几次，然后看看它如何翻译代码:

class MyList {
  int value;    // the element at the head of this list
  MyList next;  // the rest of the list

  MyList(int value, MyList next) {
    this.value = value;
    this.next = next;
  }
}

基本情况“空列表”只是一个 null 引用。使用相同模式递归表达的元素移除问题变为:

A copy of a list with an element removed is either a) the rest of the list following the head in the case that the element to be removed is the head or b) a copy of the current node followed by a copy the rest of the list with the desired element removed.

在这里，我使用同一事物的较小版本定义“删除了一个元素的列表的副本”。情况 a) 是基本情况。固定位是在不是removeee时复制头部。

当然还有另一种基本情况:如果列表为空，则无法找到removeee。这是一个错误。

将其放入代码中:

MyList removeNumber(MyList m, int removee) {
  if (m == null) throw new RuntimeException("removee not found");
  if (m.value == removee) return m.next;
  return new MyList(m.value, removeNumber(m.next, removee));
}

使用该函数看起来像这样:

MyList originalList = ... // list of 1 to 5.
MyList newListWith3removed = removeNumber(originalList, 3);

System.out.println("Original list:");
for (MyList p : originalList) System.out.println(p.value); 
System.out.println("With 3 removed:");
for (MyList p : newListWith3removed) System.out.println(p.value);

输出将如预期所示:第一个列表中为 1 到 5，第二个列表中为 1,2,4,5。 IE。第一个列表未更改。