实验题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)。

相关问题

编写一个程序exp5-2.py，用递归求解单链表中倒数第K个结点.

好的，下面是exp5-2.py的代码：

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def findKthToTail(head, k):
    if not head or k == 0:
        return None

    fast = head
    slow = head

    for i in range(k):
        if not fast:
            return None
        fast = fast.next

    while fast:
        fast = fast.next
        slow = slow.next

    return slow

# 测试代码
if __name__ == '__main__':
    # 创建单链表 1 -> 2 -> 3 -> 4 -> 5 -> 6
    head = ListNode(1)
    p = head
    for i in range(2, 7):
        node = ListNode(i)
        p.next = node
        p = p.next

    # 测试用例
    print(findKthToTail(head, 0)) # None
    print(findKthToTail(head, 1).val) # 6
    print(findKthToTail(head, 3).val) # 4
    print(findKthToTail(head, 6).val) # 1
    print(findKthToTail(head, 7)) # None

该程序使用了双指针法，其中一个指针先走k步，然后两个指针同时往后走，当先走的指针到达链表末尾时，后走的指针就指向了倒数第k个节点。如果遍历完整个链表，先走的指针仍然没有到达末尾，那么就说明k大于链表长度，返回None。

假设单链表中存放的是整数 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;
}