用递归方法求单链表中的倒数第k个节点
时间: 2023-10-10 09:11:54 浏览: 65
递归方法求单链表中的倒数第k个节点可以通过如下步骤实现:
1. 定义一个全局变量count,表示当前递归到的节点在链表中的位置。
2. 从链表头节点开始递归,如果当前节点为空,则返回空指针。
3. 递归调用下一个节点。
4. 在递归返回时,count加1。
5. 如果count等于k,则返回当前节点。
6. 否则,继续递归下一个节点。
代码如下:
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
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;
}
```
在主函数中调用该函数,如下所示:
```
ListNode *head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
int k = 2;
ListNode *node = findKthToTail(head, k);
if (node != nullptr) {
cout << "倒数第" << k << "个节点的值为:" << node->val << endl;
} else {
cout << "链表长度小于" << k << endl;
}
```
输出结果为:
```
倒数第2个节点的值为:4
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)