Java如何迭代和遞歸地在鏈表中查找值

Question

我有一個方法，它有一個鏈接列表和一個int值的引用。所以，這個方法會計算並返回值在鏈表中發生的頻率。所以，我決定做一個類，

public class ListNode{ 
public ListNode (int v, ListNode n) {value = v; next = n;) 
public int value; 
public ListNode next; 
} 

然後，該方法將與

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

所以開始，我改變了這一部分，如果我這樣做遞歸，那麼我將不得不

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

那麼，現在是遞歸部分嗎？

Answer 1

你需要以某種方式知道你的列表結束。我們假設（因爲這是最簡單的方法），最後一個節點next設置爲空。然後，您可以使用它作爲檢查何時停止迭代：

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

同樣的方法可用於遞歸解決方案，但它是一個有點混亂，因爲你需要通過你的count作爲參數傳遞給您的遞歸函數呼叫。

Answer 2

爲了讓你開始，你會發現，如果你使用非空ListNode運行你的findValue方法，你將觸發一個無限循環。您需要在每次遞歸時將節點移動到next。

Answer 3

這看起來像在您的示例代碼中的錯誤：

return findValue(x, valueToCount +1); 

你應該增加計，不被搜索的值。另外不要忘記移動到下一個節點！所以這應該是：

return 1 + findValue(x.next, valueToCount); 

Answer 4

小利斯佩爾路徑：

1. 什麼是空的結果 - 空

2. 什麼是找到一個正常的節點的結果 -

   if (node.value == aValue) 
       return true; 
   

   if if

3. 別的嘗試下一個節點遞歸

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