已知一个带有表头结点的单链表,结点结构为(data,link),假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0。
时间: 2024-05-04 08:20:26 浏览: 265
这道题可以使用双指针的方法来解决。首先让快指针先走 k 步,然后慢指针和快指针一起向前走,直到快指针到达链表的末尾。此时慢指针所指的位置就是倒数第 k 个位置上的结点。
算法的具体实现如下:
1. 定义快指针 fast 和慢指针 slow,都指向头结点;
2. 让快指针先走 k 步;
3. 然后快指针和慢指针一起向前走,直到快指针到达链表的末尾;
4. 如果此时慢指针仍然指向头结点,说明链表中没有倒数第 k 个结点,返回 0;
5. 否则,输出慢指针所指的结点的 data 域,并返回 1。
下面是算法的实现代码:
```
int findKthLast(Node *list, int k) {
Node *fast = list, *slow = list;
for (int i = 0; i < k; i++) {
if (fast == NULL) return 0; // 链表长度小于 k
fast = fast->link;
}
while (fast != NULL) {
fast = fast->link;
slow = slow->link;
}
if (slow == list) return 0; // 链表中没有倒数第 k 个结点
printf("%d\n", slow->data); // 输出倒数第 k 个结点的 data 域
return 1;
}
```
阅读全文