c++ - 使用递归查找单个链表中倒数第 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，因为我会在返回之前再添加 1 五次。我该如何解决这个问题？

此外，我不确定这是否可行，但是有没有一种方法可以使用递归返回指向倒数第 n 个节点的指针。我看不到使用单链表执行此操作的方法。

Answer 1

不要对两个不同的事物使用相同的变量，而要使用两个不同的变量。通过引用传递一个整数，以跟踪您距离末尾有多少个节点，并使用 return 作为结果。

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