递归地从链接列表中删除节点 [英] Remove node from linked list recursively

问题描述

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

Given the head of a linked list and the int to search for as parameters, I need a method that will remove the first occurrence of this number in the list, and return the modified list. however i cannot modify the original list. I know how to remove the node from the list, but im not sure how i would keep the original list intact since this has to be done recursively. below is the method ** initially M is the original list. I dont know that it will still be the same list after calling the method again...?

MyList removeNumber(MyList m, int removee){

推荐答案

想法是，结果结构将为"Y":一个两头列表(实际上是一个简单的图形).

The idea is that the resulting structure will be a "Y": a two-headed list (actually a simple graph).

Y的一个分支是原始列表.另一个是已删除节点的新列表.Y的垂直杆是删除元素之后的位置.这两个列表是通用的.这是一些带Y的侧面的ascii艺术，其中显示了从1到5的列表，其中删除了3.

One branch of the Y is the original list. The other is your new list with removed node. The vertical stalk of the Y is what's after the element you remove. It's common to both lists. Here's some ascii art with the Y turned on its side showing a list of 1 to 5 with 3 removed.

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

以递归方式进行思考就是根据一个较小的自身版本和固定的工作量来定义问题.而且您需要一个基本案例(或几个案例).

Thinking recursively is all about defining a problem in terms of a smaller version of itself plus a fixed bit of work. And you need a base case (or maybe several).

链表本身就是递归结构:

A linked list is itself a recursive structure:

列表要么是空的，要么是通过其下一个"引用链接到列表的元素.

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

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

Note this defines a list using a smaller list. The base case is the empty list. The fixed bit is the element.

多次阅读此定义，然后查看其如何翻译代码:

Read this definition a few times, then see how it translates the code:

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 引用.使用相同模式递归表示的元素去除问题变为:

The base case "empty list" is just a null reference. The element removal problem expressed recursively using the same pattern becomes:

已删除元素的列表的副本是a)如果要删除的元素是head，则列表的其余部分在head后面；或者b)当前节点的副本，然后是副本.该列表的其余部分已删除了所需的元素.

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)是基本情况.固定位是在不是是 removee 时复制的头部.

Here I'm defining a "copy of a list with one element removed" using a smaller version of the same thing. Case a) is the base case. The fixed bit is copying the head when it's not the removee.

当然还有另一种基本情况:如果列表为空，则找不到 removee .这是一个错误.

Of course there's another base case: if the list is empty, the removee can't be found. That's an error.

将其放入代码中

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

放置要使用的功能将如下所示:

Putting the function to use would look something like this:

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.第一个列表不变.

The output will look as expected: 1 to 5 in the first list and 1,2,4,5 in the second. I.e. the first list is unchanged.

这篇关于递归地从链接列表中删除节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！