已知一个带有表头结点的单链表, 假设该链表只给出了头指针 。在不改变链表的前提下,请设计一个尽可能高效的算法,对链表仅进行一遍扫描,查找链表中倒数第 个位置上的结点( 为正整数)。若查找成功,算法输出该结点的 域的值,并返回1;否则,只返回0。用c语言数据结构的代码写
时间: 2024-12-15 15:24:00 浏览: 17
带表头结点的单链表
要解决这个问题,我们可以使用快慢指针的方法。首先创建两个指针,快指针先走 k 步,然后两者同时开始移动,当快指针到达链表尾部时,慢指针会恰好停在倒数第 k 个节点上。如果找到了倒数第 k 个节点并且可以访问其值,返回 1,否则返回 0。
以下是 C 语言的解决方案:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
int findKthToTail(ListNode* head, int k) {
if (head == NULL || k <= 0) return 0; // 链表为空或k值无效
ListNode* slow = head;
ListNode* fast = head;
for (int i = 0; i < k - 1 && fast != NULL; ++i) {
fast = fast->next;
}
if (fast == NULL) return 0; // 快速指针已经到了链表尾部,但没超过k步
while (fast != NULL) {
slow = slow->next;
fast = fast->next;
}
// 检查slow指针是否可达并获取值
if (slow != NULL && slow->next != NULL) {
printf("The value of the %dth node from the tail is: %d\n", k, slow->val);
return 1;
} else {
return 0;
}
}
// 创建示例链表函数,这里省略
void createLinkedList(ListNode** head, int n, ...) {
// 生成链表并设置值...
}
int main() {
ListNode* head = NULL;
int n, k;
// 输入链表长度和k值
scanf("%d%d", &n, &k);
// 初始化链表
createLinkedList(&head, n);
int result = findKthToTail(head, k);
if (result == 1)
printf("Success\n");
else
printf("Failed\n");
return 0;
}
```
这个算法的时间复杂度是 O(n),其中 n 是链表的实际长度,因为它最多遍历整个链表两次。空间复杂度是 O(1),因为我们只用了几个额外的指针变量。
阅读全文