getLastIndexOf(int item) 链表

Question

我目前是一名 comp sci 新生，通过 class 和在线学习数据结构。

我也是堆栈的新手，但它在过去帮助了我很多。

我当前的问题是通过 LinkedList 搜索到 return 数字出现在列表中的最后一个索引。

我觉得这在某种程度上与递归和不断搜索有关，直到您可以某种方式检查确定那是该项目的最后一次出现，然后 return 它的索引。

但是我的第一个学期 Java 课程根本没有涉及递归，我有点不知所措。

在这些课程中，我不要求直截了当的答案，我只需要一些指导。或者让我放心，我在研究递归方面完全正确？

此外，这是我到目前为止所做的尝试。感谢您的帮助！

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last
    Node current;
    current = head;
    int count = 0; //count variable 
    while (current.next != null) { //go through list
        if (current.dataItem == lastItem) { 
            //check rest of the list for if that number exists beyond
        }
        count++; //increment count for every time loop executes
        current = current.next; //moves onto next node to check
    }
    return -1;
}

Answer 1

当你有这样的匹配时，你可以只保存并覆盖索引：

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last
    Node current;
    current = head;
    int count = 0; //count variable
    int lastIndex = 0;
    while (current.next != null) { //go through list
        if (current.dataItem == lastItem) { 
                lastIndex = count;
        }
        count++; //increment count for every time loop executes
        current = current.next; //moves onto next node to check
    }
return lastIndex;

所以你会在 lastIndex 中保存匹配的位置，如果有多个匹配，你会用 "latest" 值覆盖它。

Answer 2

将列表视为一个节点，后面跟着另一个列表，称为尾部。这是伪代码，注意你需要两种方法，private 一个取一个节点，这是子列表。

public int getLastIndexOf(value) {
    return getLastIndexOf(head, value);
}

private int getLastIndexOf(sublist, value) {
    //check the tail first (because we want last index)
    if (sublist.tail != null) {//list has a tail
        int lastIndexInTail = getLastIndexOf(sublist.tail, value); //recursion
        if(lastIndexInTail != -1)
          return lastIndexInTail + 1; //it's in the sub list, the sub list starts at idx 1
    }

    // it's not in the tail, check this head
    if (sublist.data == value){
      return 0; //it's at the front of this list
    }

    return -1; //it's not in the head or in the tail of sublist
}

Answer 3

如果要递归

Topcoder 中的这篇教程在这里可能会有用。

我的 2 美分如下：

递归和迭代（循环，如 for、while 等）可以用来解决您当前的问题。

您当前的代码不是递归的，而是迭代的。当您一次又一次地调用相同的函数直到某个结束条件时，就会发生递归。

一个递归函数有两部分：

基本条件 - 告诉您何时停止递归
递归条件 - 告诉你什么时候进行递归

让我们看一个例子。假设您要打印 "Hello World" 10 次。以下是您将如何迭代地完成它

for(int i = 0; i < 10; i++){
   System.out.println("Hello World");
}

这是递归的方式

void helloWorldPrinter(int index){
   //This is the base condition, tells us to stop when we've reached 10
   if(index == 10){
      return;
   }
   else{
      //Print for the n th hello world
      System.out.println("Hello World");
      //call the same function for printing the next (n+1 th) hello world
      helloWorldPrinter(index+1); //Looks similar to the i++ in the loop right?
   }
}

递归在二叉树中非常有用，二叉树是一种看起来像倒置树的数据结构。在编写迭代与递归代码时，您可以牢记的一个概念是，迭代就像以观察者的身份查看数据结构，并对 it.Recursion 执行操作就像您一样是数据结构中的一个元素 - 你做你的工作并将责任传递给下一个元素（下一个递归调用）

现在我相信您可以将此逻辑扩展到查找链表中的最后一项。尽管对此的迭代解决方案比递归解决方案容易得多。

逻辑是：

Loop over list (iterative or recursive)
  If element is found, note down the index
End Loop if list has been traversed completely
return the element index

getLastIndexOf(int item) 链表

getLastIndexOf(int item) LinkedList

java

recursion

data-structures

lastindexof