java – 递归地在链表中找到第n个元素

发布时间：2020-12-14 05:30:39 所属栏目：Java 来源：网络整理

导读：我正在练习基本的数据结构的东西,我在递归方面有一些困难.我理解如何通过迭代来做到这一点,但是我通过递归将所有从最后一个链表返回第n个节点的尝试都会导致null.这是我的代码到目前为止 public static int i = 0; public static Link.Node findnthToLastRec

我正在练习基本的数据结构的东西,我在递归方面有一些困难.我理解如何通过迭代来做到这一点,但是我通过递归将所有从最后一个链表返回第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;
}

解决方法

你需要结束,然后计算你的方式,确保每次传回回传节点.我喜欢一个回归点

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!