Rekursiv finden der N-te bis Letzte element in verketteter Liste

Ich bin üben grundlegende Datenstruktur Sachen und ich habe einige Schwierigkeiten mit Rekursion. Ich verstehe, wie zu tun dies durch iteration, aber alle meine versuche, die Rückkehr der N-te Knoten aus dem letzten eine verkettete Liste mittels Rekursion Ergebnis null. Das ist mein code bisher:

public static int i = 0; 
public static Link.Node findnthToLastRecursion(Link.Node node, int pos) {
    if(node == null) return null; 
    else{
    findnthToLastRecursion(node.next(), pos);
    if(++i == pos) return node; 
    return null; 
    }

Kann mir jemand helfen, zu verstehen, wo ich bin läuft hier falsch?

Dies ist mein iterative Lösung, welche gut funktioniert, aber ich würde wirklich gerne wissen, wie übersetzt man dies in die Rekursion:

public static Link.Node findnthToLast(Link.Node head, int n) {
    if (n < 1 || head == null) {
        return null;
    }
    Link.Node pntr1 = head, pntr2 = head;
    for (int i = 0; i < n - 1; i++) {
        if (pntr2 == null) {
            return null;
        } else {
            pntr2 = pntr2.next();
        }
    }
    while (pntr2.next() != null) {
        pntr1 = pntr1.next();
        pntr2 = pntr2.next();
    }
    return pntr1;
}

Was ist der Wert von node beim ersten Aufruf - und arbeiten Sie sich vorwärts oder rückwärts? Ich hätte gedacht, dass Sie brauchen, um zu starten am Ende und rufen previous() oder wenn Sie nicht wissen, was das Ende ist, am Anfang beginnen, arbeiten Sie Ihren Weg bis zum Ende, dann wieder raus n Zeiten. Dieser code tut nichts, wie die...
Wie Sie wissen, die letzten N-TEN Knoten, wenn Sie nicht finden, wo der Letzte Knoten ist (oder die Größe)? Diese (wenn richtig geschrieben) finden die N - 1 Knoten (nicht die x-te Letzte Knoten)
kurze Frage: wissen Sie, was die Länge der verketteten Liste, ist
Der erste Wert ist der Kopf, und es gibt keine früheren () - Funktion aufrufen. Am Anfang, arbeiten, Weg, zu Ende, dann zieht sich n-mal macht Sinn für mich, durch iteration, aber ich kann einfach nicht scheinen zu wickeln meinem Kopf auf, wie zu tun, dass rekursiv.
In diesem Fall weiß ich die Länge, aber ich versuche, es zu schreiben, unter der Annahme, dass die Länge unbekannt ist.
ich persönlich glaube nicht, dass es eine gute Möglichkeit, dies zu tun rekursiv. Ja, es gibt Möglichkeiten, aber keiner von Ihnen sind gut
der zurückgegebene Knoten aus, wenn ich und pos sind gleich, ist nie wieder in den stack. Siehe meine Antwort unten.
So Stelle ich mir vor Sie erhalten eine Liste der Elemente, wenn Sie es passieren findnthToLast(lst, 1) aber nach der iterativen Lösung haben Sie die for-Schleife wird verlassen, da der test 0 < 1-1 wird nicht passieren. Ist das ein Fehler?
Hm, gut zu fangen. Ich habe switch zu testen, mit 1, und es ist Rückkehr die richtige. Eigentlich bin ich ein bisschen verwirrt, warum jetzt. . .
Ich habe funktioniert, weil Sie nicht überprüfen pntr2 != null aber pntr2.next() 🙂

InformationsquelleAutor user3029486 | 2013-11-25

Müssen Sie bis zum Ende zu gehen und dann zählen Sie Ihre Weise zurück, stellen Sie sicher, pass zurück, den Knoten jedes mal, wenn Ihr wieder vergangen. Ich mag eine Rückkehr Punkt

public static int i = 0;  
public static Link.Node findnthToLastRecursion(Link.Node node, int pos) {

    Link.Node result = node;

    if(node != null) {
        result = findnthToLastRecursion(node.next, pos);

        if(i++ == pos){
            result = node;
        }
    }
    return result;
}

Beispiel arbeiten Ausgänge 7 als 2 Weg von der 9. und letzten Knoten:

public class NodeTest {

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    Node first = null;
    Node prev = null;
    for (int i = 0; i < 10; i++) {

        Node current = new Node(prev, Integer.toString(i),null);
        if(i==0){
            first = current;
        }
        if(prev != null){
            prev.next = current;
        }
        prev = current;
    }

    System.out.println( findnthToLastRecursion(first,2).item);
}

public static int i = 0;

public static Node findnthToLastRecursion(Node node, int pos) {

    Node result = node;

    if (node != null) {
        result = findnthToLastRecursion(node.next, pos);

        if (i++ == pos) {
            result = node;
        }
    }

    return result;
}
}

Dies sollte die Antwort akzeptiert, da die Rekursion ohne eine helper-Funktion veranschaulicht, ein besseres Verständnis von Rekursion, wenn es eine interview-Frage.
Gut, die Helfer hier ist die static int i. Diese kann getan werden, ohne statische Variablen: stackoverflow.com/a/29937328/885464

InformationsquelleAutor Sam Nunnally

4

Keine Notwendigkeit für statische Variablen.
```
public class List {
    private Node head = null;

    //[...] Other methods

    public Node findNthLastRecursive(int nth) {
        if (nth <= 0) return null;
        return this.findNthLastRecursive(this.head, nth, new int[] {0});
    }

    private Node findNthLastRecursive(Node p, int nth, int[] pos) {
        if (p == null) {
            return null;
        }
        Node n = findNthLastRecursive(p.next, nth, pos);
        pos[0]++;
        if (pos[0] == nth) {
            n = p;
        }
        return n;
    }
}
```
- Was ist der Unterschied zwischen einer statischen variable und fügt ein zusätzliches argument/mit einer helper-Funktion? Ich sehe nicht ein, warum die letztere soll besser sein als die früheren.
- Natürlich mit Hilfe einer static-variable arbeiten würde, aber das wäre nicht perfekt rekursive Ansatz streng genommen. Mit dem stack zu behalten, den aktuellen Stand der Rekursion ist in der Regel als die gängige Praxis.
- Ich meine, Sie sind auch mit einer weiteren variable, nennen Sie es pos. Unabhängig davon, ob es statisch ist oder übergeben Sie es herum, von Anruf zu Anruf ändert sich nicht viel. In anderen Worten, beide Methoden resort, um zusätzliche Variablen über den call-stack. Siehst du was ich meine?
InformationsquelleAutor Lorenzo Polidori

Ich falsch verstanden, die Frage. Hier ist eine Antwort, basierend auf Ihren iterative Lösung:

public static Link.Node findnthToLast(Link.Node head, int n) {
    return findnthToLastHelper(head, head, n);
}

private static Link.Node findnthToLastHelper(Link.Node head, Link.Node end, int n) {
    if ( end == null ) {
        return ( n > 0 ? null : head);
    } elseif ( n > 0 ) {
        return findnthToLastHelper(head, end.next(), n-1);
    } else {
        return findnthToLastHelper(head.next(), end.next(), 0);
    }
}

InformationsquelleAutor Sylwester

Können Sie dies tun, ein paar Möglichkeiten:

recurse durch die Liste einmal um die Liste der verfügbaren Länge, dann schreiben Sie eine rekursive Methode zum zurückgeben der k^th - element (eine viel einfachere problem).

verwenden Sie einen auxiliary-Struktur zu halten, das Ergebnis plus die restliche Länge; dies ersetzt im wesentlichen die zwei rekursionen der ersten option, mit einem einzigen Rekursion:

static class State {
    Link.Node result;
    int trailingLength;
}
public static Link.Node findnthToLastRecursion(Link.Node node, int pos) {
    if(node == null) return null;
    State state = new State();
    findnthToLastRecursion(node, pos, state);
    return state.result;
}

private static void findnthToLastRecursion(Link.Node node, int pos, State state) {
    if (node == null) {
        state.trailingLength = 0;
    } else {
        findnthToLastRecursion(node.next(), state);
        if (pos == state.trailingLength) {
            state.result = node;
        }
        ++state.trailingLength;
    }
}

InformationsquelleAutor Ted Hopp

eigentlich brauchen Sie nicht zu haben public static int i = 0; . für utill Methode der pos ist :

pos = verkettete Liste der Länge - pos aus dem letzten + 1

public static Node findnthToLastRecursion(Node node, int pos) {
    if(node ==null){ //if null then return null
        return null;
    }
    int length = length(node);//find the length of the liked list
    if(length < pos){
        return null;
    }
    else{
        return utill(node, length - pos + 1);
    }
}
private static int length(Node n){//method which finds the length of the linked list
    if(n==null){
        return 0;
    }
    int count = 0;
    while(n!=null){
        count++;
        n=n.next;
    }
    return count;
}
private static Node utill(Node node, int pos) {
    if(node == null) {
        return null;
    }
    if(pos ==1){
        return node;
    }
    else{
        return utill(node.next, pos-1);   
    }
}

Hier node.next ist die next Knoten. Ich bin direkt auf die next Knoten zu fordern, anstatt die next() Methode. Hoffe, es hilft.

N-TEN auf die letzten, nicht die x-te
korrigiert die Fehler.
Danke, das macht viel mehr Sinn jetzt. Sieht aus wie zu wissen, die Länge und die Verwendung einer aux-Funktion sind der Schlüssel dazu.
sehr wahr.

InformationsquelleAutor Trying

Diese cheats (leicht), aber es sieht gut aus.

public class Test {
  List<String> list = new ArrayList<> (Arrays.asList("Zero","One","Two","Three","Four","Five","Six","Seven","Eight","Nine","Ten"));
  public static String findNthToLastUsingRecursionCheatingALittle(List<String> list, int n) {
    int s = list.size();
    return s > n
            //Go deeper!
            ? findNthToLastUsingRecursionCheatingALittle(list.subList(1, list.size()), n)
            //Found it.
            : s == n ? list.get(0)
            //Too far.
            : null;
  }
  public void test() {
    System.out.println(findNthToLastUsingRecursionCheating(list,3));
  }

  public static void main(String args[]) {
    new Test().test();
  }
}

Er druckt:

Eight

welche ich nehme an das ist richtig.

Ich verwenden List statt einige LinkedList Variante, weil ich will nicht alles neu erfinden.

BTW: sollten Sie überprüfen, dieser aus.

InformationsquelleAutor OldCurmudgeon

int nthNode(struct  Node* head, int n)
{
    if (head == NULL)
        return 0;
    else {
    int i;
    i = nthNode(head->left, n) + 1;
    printf("=%d,%d,%d\n", head->data,i,n);
    if (i == n)
        printf("%d\n", head->data);
    }
}

InformationsquelleAutor bicepjai

public class NthElementFromLast {
public static void main(String[] args) {
    List<String> list = new LinkedList<>();
    Stream.of("A","B","C","D","E").forEach(s -> list.add(s));
    System.out.println(list);
    System.out.println(getNthElementFromLast(list,2));

}

private static String getNthElementFromLast(List list, int positionFromLast) {
    String current = (String) list.get(0);
    int index = positionFromLast;

    ListIterator<String> listIterator = list.listIterator();
    while(positionFromLast>0 && listIterator.hasNext()){
        positionFromLast--;
        current = listIterator.next();
    }
    if(positionFromLast != 0) {
        return null;
    }
    String nthFromLast = null;
    ListIterator<String> stringListIterator = list.listIterator();
    while(listIterator.hasNext()) {
        current = listIterator.next();
        nthFromLast = stringListIterator.next();
    }
    return nthFromLast;
}

}

Das finden der N-te element aus der letzten.

InformationsquelleAutor i_am_zero

Mein Ansatz ist einfach und geradlinig,können Sie die array-Größe, die je nach Ihrer Anforderung:

int pos_from_tail(node *k,int n)
{   static  int count=0,a[100];
    if(!k) return -1;
    else
    pos_from_tail(k->next,n);
    a[count++]=k->data;
    return a[n];
}

InformationsquelleAutor Jagmohan Singh

Müssen Sie geringfügige änderungen im code:

public static int i = 0; 
public static Link.Node findnthToLastRecursion(Link.Node node, int pos) {
    if(node == null) return null; 
    else{
        **Link.Node temp = findnthToLastRecursion(node.next(), pos);
        if(temp!=null)
            return temp;**
        if(++i == pos) return node; 
          return null; 
    }
}

InformationsquelleAutor Amit Agarwal

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.