使用递归在单个链表中查找第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,我最终会返回85,因为n = 2而不是80,因为我会在返回之前再添加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;
}