使用递归在单个链表中查找第n到最后一个节点

Question

我知道这个问题已经问过了，但我想用递归来解决它。列表中的每个节点都包含一个整数值(int val)。我想要返回整数值，而不仅仅是打印它。我想到了以下内容:

int findKthNode (node* head, int n){
    if(!head)
        return 1;
    int retval = findkthNode(head->next, n);
    if(retval==n)
        return head->val;
    return 1+retval;
}

到达列表末尾时，返回1。之后，我在之前的返回值上加1，直到到达从末尾开始的第n个节点。在这一点上，我返回那个节点上的int值。这种方法有一个问题。我继续加1，直到返回到第一个调用。如果列表是1,5,10,20,40,80,100，那么对于n=2，我最终会返回85，而不是80因为在返回之前我要加5次1。我该如何解决这个问题?

另外，我不确定这是否可能，但是是否有一种方法可以使用递归返回指向第n个最后节点的指针。

Answer 1

不要对两个不同的东西使用相同的变量，使用两个不同的变量。通过引用传递一个整数，以跟踪从末尾开始有多少个节点，并使用返回结果。

node* findKthNode (node* head, int find, int& found){
    if(!head) {
        found = 1;
        return head;
    }
    node* retval = findkthNode(head->next, find, found);
    if(found==find)
        retval = head;
    found = found + 1;
    return retval;
}

Answer 2

下面将返回一个指针，指向最后一个节点的第n个，如果没有足够的节点，则返回NULL。

node* findKthNode(node* head, int n)
{
    node* rslt = NULL;
    doFind(head, n, &rslt);
    return rslt;
}
int doFind(node* head, int n, node** rslt)
{
    if (head == NULL)
    {
        return 0;
    }
    int ret = doFind(head->next, n, rslt);
    if (ret == n)
    {
        *rslt = head;
    }
    return ret + 1;
}

在此例中，n是基于0的。要找到列表末尾的项目，你可以这样写:

node* rslt = findKthNode(head, 0);

Answer 3

需要两个"返回值"。一个用于返回的值，另一个用于返回的深度。我会在方法签名中添加一个int* depth参数来"返回"深度。