logo标签列表

在链表中递归查找倒数第n个元素

javarecursionlinked-list
12

我正在练习基本的数据结构，但是在递归方面遇到了一些困难。 我明白如何通过迭代来实现，但是我的所有尝试通过递归返回链表中倒数第n个节点都会返回空值。这是我目前的代码：

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;
}
第一次调用时，“node”的值是多少-您是向前还是向后工作？我原以为你需要从末尾开始调用“previous（）”，或者如果你不知道结尾在哪里，就从开头开始，沿着路径到达结尾，然后向外返回n次。这段代码与此毫不相同... - Floris
1
当你不知道最后一个节点在哪里（或者大小）时，如何找到倒数第n个节点？这个代码（如果正确编写）将会找到第n-1个节点（而不是倒数第n个节点）。 - justderb
在这种情况下，我知道长度，但我试图根据长度未知的假设来编写它。 - user3029486
1
@user3029486，就我个人而言，我认为没有一个好的递归方法可以做到这一点。是的，有方法，但它们都不是好的。 - Sam I am says Reinstate Monica
当i和pos相等时返回的节点永远不会返回到堆栈上。请参见下面的答案。 - Sam Nunnally
显示剩余5条评论
10个回答
12

你需要前往末尾，然后往回计数，确保每次传递回节点时都要传递回。我喜欢一个返回点。

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

工作示例输出数字7，表示它距离第9个和最后一个节点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;
}
}
2
这应该是被接受的答案，因为如果这是一个面试问题，没有辅助函数的递归展示了更好的递归理解。 - OpenUserX03
@OpenUserX03 嗯，这里的辅助变量是 static int i。这也可以在没有静态变量的情况下完成：https://dev59.com/WGIj5IYBdhLWcg3wfVJ8#29937328 - Lorenzo Polidori
4
无需静态变量。
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;
    }
}
静态变量和添加额外参数/使用帮助函数有何区别？我不明白后者为什么比前者更好。 - michal
1
当然，使用静态变量可以解决问题，但严格来说这并不是完全递归的方法。通常认为使用堆栈来保持递归的当前状态是一种常见做法。 - Lorenzo Polidori
我的意思是，您还使用了一个额外的变量，称之为pos。无论它是静态的还是从调用到调用传递，都不会有太大变化。换句话说，这两种方法都需要在调用堆栈之外使用额外的变量。您明白我的意思吗？ - michal
我认为这种方法更好，因为它避免了在类级别添加静态变量。 "findNthRecursive（）"函数很可能仅是“LinkedList”类中的几个其他成员函数之一。因此，仅为此函数在类级别上添加静态变量似乎不够干净/简单。话虽如此，我还不清楚pos为什么需要是int []类型。为什么不能只是一个int？ - venk
2
你可以用以下几种方法实现这个功能：
  1. recurse through the list once to find the list length, then write a recursive method to return the kth element (a much easier problem).

  2. use an auxiliary structure to hold the result plus the remaining length; this essentially replaces the two recursions of the first option with a single recursion:

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

我误解了问题。以下是基于您迭代解决方案的答案：

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

你需要对代码进行一些小改动：

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

实际上你不需要有 public static int i = 0;。对于 utill 方法，pos 是：

pos = 链表长度 - 从末尾数的位置 + 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);   
    }
}

这里的node.next是下一个节点。我直接访问了next节点，而不是调用next()方法。希望能有所帮助。

倒数第N个; 而不是第N个 - Sam I am says Reinstate Monica
谢谢，现在这个问题更加清晰了。看起来知道长度并使用辅助函数是解决这个问题的关键。 - user3029486
@user3029486 非常正确。 - Trying
0

这有点作弊，但看起来不错。

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

它打印：

Eight

我想这是正确的。

我使用了 List 而不是一些 LinkedList 变体，因为我不想重新发明轮子。

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

}

这将从末尾找到第N个元素。

0

我的方法很简单直接，您可以根据需要更改数组大小：

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];
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接