C语言编写一个程序,实现查找单链表中倒数第K个节点的操作,并输出该节点的数据
时间: 2024-12-15 17:16:44 浏览: 24
在C语言中,你可以使用双指针法(快慢指针)来实现查找单链表中倒数第K个节点。首先,创建两个指针,一个普通速度(慢指针),另一个速度快两步(快指针)。当快指针到达链表尾部时,慢指针就指向了倒数第二的位置。然后,将慢指针向前移动K步,即可找到倒数第K个节点。
以下是一个简单的C语言示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// 查找倒数第k个节点
Node* findKthFromEnd(Node* head, int k) {
if (head == NULL || k <= 0) {
printf("Invalid input.\n");
return NULL;
}
Node* slow = head; // 慢指针
Node* fast = head; // 快指针
// 快速移动到链表尾部
while (fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
// 如果k大于链表长度,则返回NULL
if (k > (slow == NULL ? 0 : 1)) {
return NULL;
}
// 慢指针再前进k步,找到倒数第k个节点
for (int i = 0; i < k - 1; i++) {
slow = slow->next;
}
return slow;
}
// 打印链表元素
void printList(Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
Node* head = createNode(1); // 假设链表有三个节点:1 -> 2 -> 3
head->next = createNode(2);
head->next->next = createNode(3);
int k = 2; // 要查找的倒数位置
Node* result = findKthFromEnd(head, k);
if (result != NULL) {
printf("The data of the node at position %d from the end is: %d\n", k, result->data);
} else {
printf("No such node found.\n");
}
// 打印整个链表
printList(head);
return 0;
}
```
这个程序会输出倒数第2个节点(这里是3)的数据。注意,这里的`findKthFromEnd`函数只处理正整数`k`,并且假设输入的链表非空。对于特殊情况,你需要添加相应的错误检查。
阅读全文