java Java如何迭代和递归地在链表中找到一个值
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1547164/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java How to find a value in a linked list iteratively and recursively
提问by Roxy
I have a method that has a reference to a linked list and a int value. So, this method would count and return how often the value happens in the linked list. So, I decided to make a class,
我有一个方法，该方法具有对链接列表和 int 值的引用。因此，此方法将计算并返回值在链表中出现的频率。所以，我决定开设一个班级，
public class ListNode{
public ListNode (int v, ListNode n) {value = v; next = n;)
public int value;
public ListNode next;
}
Then, the method would start with a
然后，该方法将以
public static int findValue(ListNode x, int valueToCount){
// so would I do it like this?? I don't know how to find the value,
// like do I check it?
for (int i =0; i< x.length ;i++){
valueToCount += valueToCount;
}
So, I CHANGED this part, If I did this recursively, then I would have
所以，我改变了这部分，如果我递归地这样做，那么我会
public static int findValue(ListNode x, int valueToCount) {
if (x.next != null && x.value == valueToCount {
return 1 + findValue(x, valueToCount);}
else
return new findvalue(x, valueToCount);
SO, is the recursive part correct now?
那么，递归部分现在正确了吗？
采纳答案by ChssPly76
You need to somehow know where your list ends. Let's assume (as that's the easiest approach) that the last node has nextset to null. You would then use this as check when to stop the iteration:
您需要以某种方式知道您的列表在哪里结束。让我们假设（因为这是最简单的方法）最后一个节点已next设置为 null。然后，您将使用它来检查何时停止迭代：
public static int findValue(ListNode x, int valueToCount) {
ListNode currentNode = x;
int count = 0;
while (currentNode.next!=null) {
if (currentNode.value == valueToCount) {
count++;
}
currentNode = currentNode.next;
}
return count;
}
The same approach can be used for recursive solution, except it's a bit messier because you'll need to pass your countas parameter to your recursive function call.
相同的方法可用于递归解决方案，只是它有点混乱，因为您需要将countas 参数传递给递归函数调用。
回答by finnw
This looks like a bug in your sample code:
这看起来像是示例代码中的错误：
return findValue(x, valueToCount +1);
You should be incrementing the count, not the value being searched for. Also don't forget to move to the next node! So this should be:
您应该增加计数，而不是正在搜索的值。也不要忘记移动到下一个节点！所以这应该是：
return 1 + findValue(x.next, valueToCount);
回答by miz
Little Lisper path:
小李子路径：
What is the result of null -- null
What is find result of a normal node --
if (node.value == aValue) return true;if found
else try next node recursively
public boolean find(ListNode<T> n, T value) { if (n==null) return false; if (n.element.equals(value)) return true; else return find(n.next, value); }
null的结果是什么——null
正常节点的查找结果是什么——
if (node.value == aValue) return true;如果找到
否则递归地尝试下一个节点
public boolean find(ListNode<T> n, T value) { if (n==null) return false; if (n.element.equals(value)) return true; else return find(n.next, value); }
回答by akf
To get you started, you will find that if you run your findValuemethod with a non-null ListNodeyou will trigger an infinite loop. You will need to move your node to nexton each recursion.
为了让您开始，您会发现如果您findValue使用非空值运行您的方法，ListNode您将触发一个无限循环。您需要next在每次递归时将节点移动到。
