Java 递归查找链表中的第n个到最后一个元素

Recursively find nth to last element in linked list

提问by user3029486

I'm practicing basic data structure stuff and I'm having some difficulties with recursion. I understand how to do this through iteration but all of my attempts to return the nth node from the last of a linked list via recursion result in null. This is my code so far:

我正在练习基本的数据结构内容，但在递归方面遇到了一些困难。我知道如何通过迭代来做到这一点，但我所有尝试通过递归从链表的最后一个返回第 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; 
    }

Can anyone help me understand where I'm going wrong here?

谁能帮我理解我哪里出错了？

This is my iterative solution which works fine, but I'd really like to know how to translate this into recursion:

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

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

采纳答案by Sam Nunnally

You need to go to the end and then count your way back, make sure to pass back the node each time its passed back. I like one return point

您需要走到尽头，然后计算回去的路，确保每次传回节点时都将其传回。我喜欢一个返回点

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

Working example outputs 7 as 2 away from the 9th and last node:

工作示例输出 7 作为 2 远离第 9 个和最后一个节点：

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

回答by Trying

actually you don't need to have public static int i = 0;. for utillmethod the posis :

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

pos = linked list length - pos from last + 1

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

Here node.nextis the nextnode. I am directly accessing the nextnode rather than calling the next()method. Hope it helps.

这里node.next是next节点。我直接访问next节点而不是调用next()方法。希望能帮助到你。

回答by Ted Hopp

You can do this a couple of ways:

您可以通过以下几种方式执行此操作：

1. recurse through the list once to find the list length, then write a recursive method to return the k^thelement (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;
       }
   }
   

1. 遍历列表一次以找到列表长度，然后编写一个递归方法来返回第 k^个元素（一个更简单的问题）。

2. 使用辅助结构来保存结果加上剩余长度；这基本上用单个递归替换了第一个选项的两个递归：

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

回答by Sylwester

I misunderstood the question. Here is an answer based on your iterative solution:

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

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

回答by OldCurmudgeon

This cheats (slightly) but it looks good.

这作弊（稍微）但看起来不错。

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

It prints:

它打印：

Eight

which I suppose is correct.

我认为这是正确的。

I have use Listinstead of some LinkedListvariant because I do not want to reinvent anything.

我使用List而不是一些LinkedList变体，因为我不想重新发明任何东西。

回答by bicepjai

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

回答by akhil_mittal

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

}

}

This will find Nth element from last.

这将从最后找到第 N 个元素。

回答by Lorenzo Polidori

No need for static variables.

不需要静态变量。

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

回答by Jagmohan Singh

My approach is simple and straight,you can change the array size depending upon your requirement:

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

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

回答by Amit Agarwal

You'll have make slight changes in the 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; 
    }
}