输出单链表倒数第K个结点值
【问题描述】输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第1个节点。
【输入形式】
输入第一位为K值，其后接一串以空格分隔的整型值。
【输出形式】
输出为倒数第K个结点的值，若无，则输出Not Found
【样例输入】
3 13 45 54 32 1 4 98 2
【样例输出】
4
【样例说明】
K值为3，则输出链表倒数第3个结点的值，为4；数据输入间以空格隔开
【评分标准】
本题要综合输出正确性及使用的数据结构。需由输入数据构建单链表。不使用链表的将不得分。
这题用C怎么做
要在C语言中实现输出单链表倒数第K个结点值，以下是完整的代码示例和注释。该示例通过构建链表，然后利用双指针方法找到倒数第K个结点。
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建链表结点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 构建链表
Node* buildList(int* array, int size) {
if (size == 0) return NULL;
Node* head = createNode(array);
Node* current = head;
for (int i = 1; i < size; i++) {
current->next = createNode(array);
current = current->next;
}
return head;
}
// 找到倒数第K个结点
int findKthToLast(Node* head, int k) {
if (!head || k <= 0) return -1;
Node *fast = head, *slow = head;
// 快指针先走k步
for (int i = 0; i < k; i++) {
if (fast == NULL) return -1; // 链表长度不足k
fast = fast->next;
}
// 快慢指针一起走
while (fast) {
fast = fast->next;
slow = slow->next;
}
return slow->data;
}
int main() {
int k;
printf("请输入K值：");
scanf("%d", &k);
char buffer;
printf("请输入链表值：");
scanf(" %[^\n]s", buffer);
int array, size = 0;
char* token = strtok(buffer, " ");
while (token != NULL) {
array = atoi(token);
token = strtok(NULL, " ");
}
Node* head = buildList(array, size);
int result = findKthToLast(head, k);
if (result == -1) {
printf("Not Found\n");
} else {
printf("%d\n", result);
}
// 释放链表内存
Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
return 0;
}
### 代码解析
1. **链表节点的结构**：定义了一个结构体`Node`，包含整型数据`data`和指向下一个节点的指针`next`。
2. **创建节点函数**：`createNode`用于创建一个新的节点。
3. **构建链表函数**：`buildList`通过传入的数组和数组大小来构建链表。
4. **寻找倒数第K个节点函数**：
- `findKthToLast`通过使用两个指针`fast`和`slow`，利用双指针的方式找到倒数第K个结点。
- 先让`fast`指针前进K步，然后`fast`与`slow`指针同时前进，直到`fast`到达链表末尾，此时`slow`指针指向的就是倒数第K个节点。
5. **主函数**负责读取输入、构建链表、调用查找函数并输出结果，同时释放链表内存。
### 执行步骤
1. 用户输入K值和链表节点值。
2. 程序将输入的节点值存储在数组中并构造链表。
3. 调用`findKthToLast`函数查找倒数第K个节点。
4. 输出结果，若未找到则输出`Not Found`。
5. 释放动态分配的链表内存。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 本帖最后由 jackz007 于 2024-10-26 09:24 编辑
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
typedef struct chain {
int data ;
struct chain * next ;
} CHAIN , * PCHAIN ;
PCHAIN head , p , q ;
int d , i , k , n , r ;
printf("Enter the data : ") ;
for(r = 1 , n = 0 ;; n ++) {
scanf("%d" , & d) ;
if(! n) {
k = d ;
} else {
if (p = (PCHAIN) malloc(sizeof(CHAIN))) {
p -> data = d ;
p -> next = NULL ;
if(n == 1) head = p ;
else q -> next = p ;
q = p ;
} else {
fprintf(stderr , "malloc() failure !\n") ;
r = 0 ;
break ;
}
}
if(getchar() =='\n') break ;
}
if(r) {
for(i = 0 , p = head ; p && i < n - k ; i ++) p = p -> next ;
if(p) printf("%d\n" , p -> data) ;
else printf("not found !\n") ;
for(p = head ; p ; p = q ) {
q = p -> next ;
free(p) ;
}
}
}
页:
[1]