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

yangzhixiaohuli

【问题描述】

输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第1个节点。

【输入形式】

输入第一位为K值，其后接一串以空格分隔的整型值。
【输出形式】

输出为倒数第K个结点的值，若无，则输出Not Found

【样例输入】

3 13 45 54 32 1 4 98 2
【样例输出】

4
【样例说明】

K值为3，则输出链表倒数第3个结点的值，为4；数据输入间以空格隔开
【评分标准】

本题要综合输出正确性及使用的数据结构。需由输入数据构建单链表。不使用链表的将不得分。

这题用C怎么做

最佳答案

月排行榜 / 总排行榜

FishC

2024-10-25 20:09:01

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

跳转到最佳答案楼层

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

jackz007

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int main(void)
   
5. {
   
6.         typedef struct chain {
   
7.                 int data                                                            ;
   
8.                 struct chain * next                                                 ;  
   
9.         } CHAIN , * PCHAIN                                                          ;
   
10.         PCHAIN head , p , q                                                         ;
    
11.         int d , i , k , n , r                                                       ;
    
12.         printf("Enter the data : ")                                                 ;
    
13.         for(r = 1 , n = 0 ;; n ++) {
    
14.                 scanf("%d" , & d)                                                   ;
    
15.                 if(! n) {
    
16.                         k = d                                                       ;
    
17.                 } else {
    
18.                         if (p = (PCHAIN) malloc(sizeof(CHAIN))) {
    
19.                                 p -> data = d                                       ;
    
20.                                 p -> next = NULL                                    ;
    
21.                                 if(n == 1) head = p                                 ;
    
22.                                 else q -> next = p                                  ;
    
23.                                 q = p                                               ;
    
24.                          } else {
    
25.                                 fprintf(stderr , "malloc() failure !\n")            ;
    
26.                                 r = 0                                               ;
    
27.                                 break                                               ;
    
28.                         }
    
29.                 }
    
30.                 if(getchar() =='\n') break                                          ;
    
31.         }
    
32.         if(r) {
    
33.                 for(i = 0 , p = head ; p && i < n - k ; i ++) p = p -> next         ;
    
34.                 if(p) printf("%d\n" , p -> data)                                    ;
    
35.                 else printf("not found !\n")                                        ;
    
36.                 for(p = head ; p ; p = q ) {
    
37.                         q = p -> next                                               ;
    
38.                         free(p)                                                     ;
    
39.                 }
    
40.         }
    
41. }

复制代码