单链表怎么找倒数第k个节点
时间: 2023-10-10 17:12:02 浏览: 47
可以使用双指针的方式来找到单链表的倒数第k个节点。我们可以定义两个指针p和q,初始时p和q都指向链表的头节点。
1. 将指针p向前移动k个位置。
2. 然后将指针p和q同时向后移动,直到指针p到达链表的尾节点为止。
3. 此时指针q所指向的节点就是链表的倒数第k个节点。
具体实现如下:
```c++
ListNode* findKthToTail(ListNode* head, int k) {
if (head == nullptr || k <= 0) {
return nullptr;
}
ListNode* p = head;
ListNode* q = head;
for (int i = 0; i < k - 1; i++) {
if (p->next != nullptr) {
p = p->next;
} else {
return nullptr;
}
}
while (p->next != nullptr) {
p = p->next;
q = q->next;
}
return q;
}
```
时间复杂度为O(n),其中n为链表的长度。
相关问题
输入一个单链表,输出倒数第k个节点
要输出单链表的倒数第k个节点,可以使用快慢指针的思路来解决这个问题。
首先,定义两个指针slow和fast,初始时都指向链表的头节点。让fast指针先走k步,然后slow和fast指针同时向后移动,直到fast指针指向链表的最后一个节点。
由于fast指针比slow指针先走了k步,所以当fast指针指向最后一个节点时,slow指针正好指向倒数第k个节点。
具体的算法如下:
1. 定义一个计数器count并初始化为0。
2. 定义两个指针slow和fast,初始都指向链表的头节点。
3. while循环中,先判断count是否小于k。若小于,则将fast指针向后移动一步,并将count加1。
4. 当count等于k时,同时移动slow和fast指针,直到fast指针指向最后一个节点。此时slow指针指向倒数第k个节点。
5. 返回slow指针指向的节点。
以上算法的时间复杂度为O(n),其中n为链表的长度。
例如,假设链表为1 -> 2 -> 3 -> 4 -> 5,k的值为2。按照以上算法,fast指针先走两步,指向节点3,此时slow指针也指向节点3。
用递归方法求单链表中的倒数第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个节点了。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)