Java-Wie findet man einen Wert in einer verknüpften Liste iterativ und rekursiv

Habe ich eine Methode, die eine Referenz auf eine verkettete Liste und ein int-Wert. So, diese Methode würde zu zählen und zurück, wie oft der Wert geschieht in der verlinkten Liste. Also, ich beschlossen, eine Klasse,

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

Dann wäre die Methode starten Sie mit einer

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, ich habe dieses Teil, Wenn ich das Tat rekursiv, dann hätte ich

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, ist das rekursive Teil jetzt korrekt?

... und deine Frage 'würde das funktionieren?'?
ja, ich Frage mich, ob das funktionieren kann

InformationsquelleAutor Roxy | 2009-10-10

  1. 1

    Müssen Sie irgendwie wissen, wo die Liste endet. Lassen Sie uns annehmen, (wie, das ist die einfachste Methode), dass der Letzte Knoten hat next auf null gesetzt. Sie würden dann verwenden Sie diese überprüfen, wenn die zu stoppen Sie die iteration:

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

    Der gleiche Ansatz kann verwendet werden, für die rekursive Lösung, außer es ist ein bisschen messier, weil Sie brauchen werden, um Ihren pass count als parameter zu Ihrem rekursiven Aufruf der Funktion.

    Sie konnte sich nur fügen Sie eine andere int um Ihre Unterschrift machen Sie Ihre while eine if und ändern Sie die currentNode=currentNode.next; zu return findValue(x,valueToCount,count);
    das obige Beispiel hat der Zähler in der if / else - Anweisung, der Kommentar oben gibt Ihnen Hinweise zu erlassen, um eine rekursive Methode.
    Okay, danke für die Hinweise, das hat mir wirklich geholfen zu verstehen, mehr über Sie 🙂
    Whoa! Jemand ist nicht in einer guten Stimmung heute

    InformationsquelleAutor ChssPly76

  2. 1

    Dieser sieht aus wie ein bug in deinem Beispiel-code:

    return findValue(x, valueToCount +1);

    Sollten Sie die Inkrementierung der Zählung, nicht der Wert gesucht wird. Vergessen Sie auch nicht, sich zu bewegen, um den nächsten Knoten! So das sollte:

    return 1 + findValue(x.next, valueToCount);
    Java muss nicht tail-call-Beseitigung, so gibt es wenig Sinn, die übergabe der Graf als ein zusätzliches Akkumulator-parameter.
    Ok, jetzt verstehe ich, aber was ist mit der if-Anweisung. Ich denke seine falsch? sollte es sein, wenn(x ein.next == null && x.Wert != valueToCount) { return 0; } wäre das richtig?
    valueToCount ist der Wert, der gesucht wird, nicht ein Akkumulator.
    if(x.next == null...) vermissen werden der erste Knoten und nicht auf die leere Liste.

    InformationsquelleAutor finnw

  3. 1

    Wenig Lisper Pfad:

    1. Was ist das Ergebnis null -- null -

    2. Was finden Ergebnis von einem normalen Knoten --

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

      wenn gefunden

    3. anders versuchen nächsten Knoten rekursiv

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

    InformationsquelleAutor miz

  4. 0

    Bekommen Sie started, Sie werden feststellen, dass wenn Sie führen Sie Ihre findValue Methode mit einer nicht-null - ListNode Sie löst eine unendliche Schleife. Sie verschieben müssen, um Ihren Knoten zu next auf jeder Rekursion.

    InformationsquelleAutor akf

Schreibe einen Kommentar