[已解决]输出单链表倒数第K个结点值

FishC

要在C语言中实现输出单链表倒数第K个结点值，以下是完整的代码示例和注释。该示例通过构建链表，然后利用双指针方法找到倒数第K个结点。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct Node {
   
5.     int data;
   
6.     struct Node* next;
   
7. } Node;
   
8. 
   
9. // 创建链表结点
   
10. Node* createNode(int data) {
    
11.     Node* newNode = (Node*)malloc(sizeof(Node));
    
12.     newNode->data = data;
    
13.     newNode->next = NULL;
    
14.     return newNode;
    
15. }
    
16. 
    
17. // 构建链表
    
18. Node* buildList(int* array, int size) {
    
19.     if (size == 0) return NULL;
    
20.     Node* head = createNode(array[0]);
    
21.     Node* current = head;
    
22.     for (int i = 1; i < size; i++) {
    
23.         current->next = createNode(array[i]);
    
24.         current = current->next;
    
25.     }
    
26.     return head;
    
27. }
    
28. 
    
29. // 找到倒数第K个结点
    
30. int findKthToLast(Node* head, int k) {
    
31.     if (!head || k <= 0) return -1;
    
32.     Node *fast = head, *slow = head;
    
33. 
    
34.     // 快指针先走k步
    
35.     for (int i = 0; i < k; i++) {
    
36.         if (fast == NULL) return -1; // 链表长度不足k
    
37.         fast = fast->next;
    
38.     }
    
39. 
    
40.     // 快慢指针一起走
    
41.     while (fast) {
    
42.         fast = fast->next;
    
43.         slow = slow->next;
    
44.     }
    
45. 
    
46.     return slow->data;
    
47. }
    
48. 
    
49. int main() {
    
50.     int k;
    
51.     printf("请输入K值：");
    
52.     scanf("%d", &k);
    
53. 
    
54.     char buffer[1024];
    
55.     printf("请输入链表值：");
    
56.     scanf(" %[^\n]s", buffer);
    
57. 
    
58.     int array[100], size = 0;
    
59. 
    
60.     char* token = strtok(buffer, " ");
    
61.     while (token != NULL) {
    
62.         array[size++] = atoi(token);
    
63.         token = strtok(NULL, " ");
    
64.     }
    
65. 
    
66.     Node* head = buildList(array, size);
    
67.     int result = findKthToLast(head, k);
    
68.     if (result == -1) {
    
69.         printf("Not Found\n");
    
70.     } else {
    
71.         printf("%d\n", result);
    
72.     }
    
73. 
    
74.     // 释放链表内存
    
75.     Node* temp;
    
76.     while (head != NULL) {
    
77.         temp = head;
    
78.         head = head->next;
    
79.         free(temp);
    
80.     }
    
81. 
    
82.     return 0;
    
83. }

复制代码

### 代码解析
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 小助理，如未能正确解答您的问题，请继续追问。