已知一个带有表头结点的单链表,结点结构如下图。假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功,算法输出该结点的data值,并返回1;否则,只返回0。
时间: 2024-05-02 14:21:41 浏览: 98
算法思路:
1. 使用双指针法,让指针p和指针q同时指向表头结点。
2. 让指针q先走k步,然后让p和q同时向后移动,直到q指向空结点。
3. 当q指向空结点时,p所指向的结点就是倒数第k个结点。
4. 如果p指向的是头结点,则说明k的值大于链表长度,返回0;否则返回1并输出p所指向结点的data值。
算法实现:
```C++
int FindKthFromEnd(LinkList list, int k) {
if(list == NULL || list->next == NULL) //链表为空或只有一个头结点,返回0
return 0;
ListNode *p = list->next, *q = list->next; //初始化双指针
while(k--) { //让q先走k步
if(q == NULL) //如果k大于链表长度,返回0
return 0;
q = q->next;
}
while(q != NULL) { //让p和q同时向后移动,直到q指向空结点
p = p->next;
q = q->next;
}
if(p == list->next) //如果p指向的是头结点,说明k大于链表长度,返回0
return 0;
else {
printf("%d\n", p->data); //输出p所指向结点的data值
return 1;
}
}
```
阅读全文