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

相关问题

实验题6:用递归方法求单链表中的倒数第k个结点目的:掌握单链表递归算法的设计方法。 内容:编写一个程序exp5-6.cpp,用递归方法求单链表中的倒数第k个结点。综合性实验

实验题目6的目标是让学生通过递归算法理解并实现对单链表的操作，特别是找到倒数第k个节点。在这个任务中，你需要设计一个函数，它接受一个单链表的头指针和一个整数k作为输入参数，然后返回链表的倒数第k个节点。

递归思路通常是这样的：
1. 首先判断基本情况：如果链表为空或者k等于0，那么返回空或null（视语言而定）。
2. 对于非空链表，可以将问题分解为两个部分：处理当前节点之后的链表（即剩余节点），以及处理整个链表之前的部分（即前k-1个节点）。
3. 使用递归调用自身，一次前进一个节点，同时减少剩余需要查找的节点数k。
4. 当k减到1时，说明已经到达了倒数第一个节点，将其返回。

以下是简单的伪代码示例：

// 假设ListNode结构包含一个指向下一个节点的指针next，还有一个值val
ListNode* findKthFromEnd(ListNode* head, int k) {
    if (head == nullptr || k <= 0) {
        return nullptr; // 或者在某些语言中返回NULL
    }
    // 递归步骤：如果k大于1，继续在后半部分链表中寻找倒数第(k-1)个元素
    if (k > 1) {
        return findKthFromEnd(head->next, k - 1);
    } else {
        // 如果k等于1，找到了最后一个元素
        return head;
    }
}

记得在实际实现中要考虑边界条件，并确保递归能够正常结束，避免栈溢出。

假设单链表中存放的是整数 1、用递归方法求解单链表的长度； 2、用递归方法求解单链表中所有数的平均数； 3、用递归方法求单链表中倒数第k个结点元素。 实验要求：理解递归的含义，写出递归算法。

1. 用递归方法求解单链表的长度：
递归的基本思想是不断缩小问题的规模，直到问题可以简单地解决。对于单链表来说，递归的基本操作是对当前节点的下一个节点进行递归操作，直到遇到空节点时返回0，否则返回计数器加1。
下面是求解单链表长度的递归算法示例代码：

int getLength(Node *head) {
if(head == NULL) {
return 0;
}
else {
return getLength(head->next) + 1;
}
}

2. 用递归方法求解单链表中所有数的平均数：
同样地，对于单链表中所有数的平均数，可以通过递归地对每个元素进行求和操作，并记录已经操作过的节点个数，最终得出平均数。为了便于计算，可以将和的初始值设置为0，而将计数器初始值设置为1。
下面是求解单链表平均数的递归算法示例代码：

float getAverage(Node *head, int count, float sum) {
if(head == NULL) {
return sum / count;
}
else {
sum += head->data;
return getAverage(head->next, count+1, sum);
}
}

3. 用递归方法求单链表中倒数第k个结点元素:
对于单链表中倒数第k个结点元素，可以采用两个指针来实现。首先，将第一个指针指向链表头，让它先走k-1步，然后再让第二个指针从头节点开始走，两个指针一起走，直到第一个指针走到链表尾部时，第二个指针所指节点即为倒数第k个节点。
具体来说，可以使用递归算法来实现：对于每个节点，递归查找其后面的第k个节点，如果不存在，则返回空节点；否则，返回当前节点。
下面是求解单链表倒数第k个节点元素的递归算法示例代码：

Node* getKthFromEnd(Node *head, int k) {
if (head == NULL) {
return NULL;
}
Node *p = getKthFromEnd(head->next, k);
if (p == NULL) {
if (k == 1) {
return head;
}
else {
return NULL;
}
}
else {
return p;
}
}