用递归方法求单链表中的倒数第k个节点

我们可以使用双指针来解决这个问题。首先让一个指针p1指向链表的头节点，然后让它向前移动k-1步，这时再让另一个指针p2从头节点开始，然后p1和p2同时向前移动，直到p1到达链表的尾节点，此时p2所指向的节点就是倒数第k个节点。

递归方法的思路是这样的：我们定义一个全局变量count，表示当前递归到的节点的位置，然后递归到链表的尾节点时开始回溯，回溯时每经过一个节点count就加1，当count等于k时就返回该节点的值。具体实现可以参考下面的代码：

int count = 0;
ListNode* findKthToTail(ListNode* head, int k) {
    if (head == nullptr) return nullptr;
    ListNode* node = findKthToTail(head->next, k);
    count++;
    if (count == k) return head;
    return node;
}

在调用函数时，我们需要将count初始化为0，然后传入链表的头节点和k值，代码如下：

ListNode* node = findKthToTail(head, k);

这样就可以得到单链表中的倒数第k个节点了。

相关问题

假设单链表中存放的是整数 1、用递归方法求解单链表的长度； 2、用递归方法求解单链表中所有数的平均数； 3、用递归方法求单链表中倒数第k个结点元素。

1. 求单链表长度的递归方法如下：

int getLength(ListNode* head) {
    if (head == nullptr) {
        return 0;
    }
    return 1 + getLength(head->next);
}

2. 求单链表所有数的平均数的递归方法如下：

double getAverage(ListNode* head) {
    if (head == nullptr) {
        return 0;
    }
    int sum = head->val;
    int count = 1;
    if (head->next != nullptr) {
        pair<int, int> result = getSumAndCount(head->next);
        sum += result.first;
        count += result.second;
    }
    return (double)sum / count;
}

3. 求单链表中倒数第k个结点元素的递归方法如下：

ListNode* getKthFromEnd(ListNode* head, int k) {
    if (head == nullptr) {
        return nullptr;
    }
    ListNode* node = getKthFromEnd(head->next, k);
    if (node != nullptr) {
        return node;
    }
    if (k == 1) {
        return head;
    }
    return nullptr;
}

实验题2：用递归算法求单链表中倒数第K个结点。 目的：深入掌握单链表递归算法设计方法。 内容：编写一个程序exp5-2.py，用递归求解单链表中倒数第K个结点.

好的，下面是我的代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
def find_kth_node(head: ListNode, k: int) -> ListNode:
    if k <= 0 or not head:
        return None
    
    fast = slow = head
    
    for _ in range(k):
        if not fast:
            return None
        fast = fast.next
    
    while fast:
        fast = fast.next
        slow = slow.next
    
    return slow

代码思路如下：

1. 首先检查 k 是否小于等于 0 或者 head 是否为空，如果是，返回 None。
2. 定义两个指针 fast 和 slow，让 fast 先走 k 步，然后 slow 和 fast 同时移动，直到 fast 到达链表末尾。
3. 返回 slow。

这里使用了快慢指针的思想，时间复杂度为 O(n)。