6-6 LinkList6-查询单链表倒数第K个链点的元素带头结点的单链表A,头指针为h,该单链表A中存储了一系列正整数,设计算法FindInvertedK( ),查找并输出倒数第K个位置上的数字,如果K超过单链表长度,需要报错。
时间: 2023-05-21 22:04:46 浏览: 116
可以采用双指针法来解决这个问题,首先将快指针和慢指针都指向头结点,然后快指针向前移动K个位置,此时快慢指针相差K个节点。然后快指针和慢指针同时向前移动,直到快指针到达链表末尾,此时慢指针所指的位置就是倒数第K个节点。
具体的实现过程可以参考下面的代码:
```C++
int FindInvertedK(ListNode* head, int k) {
if (head == nullptr || k <= 0) {
return -1;
}
ListNode* fast = head;
ListNode* slow = head;
for (int i = 0; i < k; i++) {
fast = fast->next;
if (fast == nullptr && i != k - 1) {
return -1; // 超过了链表长度,返回-1
}
}
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
return slow->val;
}
```
在该函数中,我们首先判断链表是否为空或者k是否小于等于0,如果是则直接返回-1。然后设置快指针和慢指针都指向头结点,快指针向前移动K个位置,如果快指针到达了链表末尾而没有移动K个位置,则说明K超过了链表长度,返回-1。如果快指针在移动K个位置后还没有到达链表末尾,则快慢指针同时往前移动,直到快指针到达链表末尾为止,最后返回慢指针所指的节点的值即可。
阅读全文