java - 递归查找链表中的倒数第 n 个元素

Question

我正在练习基本的数据结构，但在递归方面遇到了一些困难。我了解如何通过迭代执行此操作，但我所有尝试通过递归从链表的最后一个节点返回第 n 个节点的结果都为 null。到目前为止，这是我的代码:

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

任何人都可以帮助我了解我哪里出错了吗？

这是我的迭代解决方案，效果很好，但我真的很想知道如何将其转化为递归:

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

Answer 1

你需要走到尽头然后倒数，确保每次传回时都传回节点。我喜欢一个返回点

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

工作示例从第 9 个和最后一个节点输出 7 作为 2:

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