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