[已解决]输出单链表倒数第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:01:32

我们可以使用C++编写一个程序，通过构建一个单向链表获取倒数第K个节点的值。以下是实现步骤和代码示例：

1. 定义链表节点的结构。
2. 创建链表并读取输入值。
3. 使用双指针方法找到倒数第K个节点。

1. #include <iostream>
   
2. #include <sstream>
   
3. #include <vector>
   
4. 
   
5. struct ListNode {
   
6.     int value;
   
7.     ListNode* next;
   
8.     ListNode(int val) : value(val), next(nullptr) {}
   
9. };
   
10. 
    
11. ListNode* createLinkedList(const std::vector<int>& values) {
    
12.     ListNode* head = nullptr;
    
13.     ListNode* tail = nullptr;
    
14.     for (int value : values) {
    
15.         ListNode* newNode = new ListNode(value);
    
16.         if (!head) {
    
17.             head = newNode;
    
18.         } else {
    
19.             tail->next = newNode;
    
20.         }
    
21.         tail = newNode;
    
22.     }
    
23.     return head;
    
24. }
    
25. 
    
26. void findKthFromEnd(ListNode* head, int k) {
    
27.     ListNode* first = head;
    
28.     ListNode* second = head;
    
29. 
    
30.     for (int i = 0; i < k; ++i) {
    
31.         if (!first) {
    
32.             std::cout << "Not Found" << std::endl;
    
33.             return;
    
34.         }
    
35.         first = first->next;
    
36.     }
    
37. 
    
38.     while (first) {
    
39.         first = first->next;
    
40.         second = second->next;
    
41.     }
    
42. 
    
43.     if (second) {
    
44.         std::cout << second->value << std::endl;
    
45.     } else {
    
46.         std::cout << "Not Found" << std::endl;
    
47.     }
    
48. }
    
49. 
    
50. int main() {
    
51.     std::string line;
    
52.     std::getline(std::cin, line);
    
53.     std::istringstream iss(line);
    
54.    
    
55.     int k;
    
56.     iss >> k;
    
57. 
    
58.     std::vector<int> values;
    
59.     int num;
    
60.     while (iss >> num) {
    
61.         values.push_back(num);
    
62.     }
    
63. 
    
64.     ListNode* head = createLinkedList(values);
    
65.     findKthFromEnd(head, k);
    
66. 
    
67.     return 0;
    
68. }

复制代码

### 代码解释
- **ListNode结构体**: 表示链表节点，包含整数值和一个指向下一个节点的指针。
- **createLinkedList函数**: 根据输入的整数数组创建链表。
- **findKthFromEnd函数**: 使用双指针方法找到倒数第K个节点。
  - 第一个指针先移动K步，然后两个指针同时移动，直到第一个指针到达末尾。
  - 此时，第二个指针所指即为倒数第K个节点。
- **main函数**: 处理输入，创建链表并调用查找函数。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

我们可以使用C++编写一个程序，通过构建一个单向链表获取倒数第K个节点的值。以下是实现步骤和代码示例：

1. 定义链表节点的结构。
2. 创建链表并读取输入值。
3. 使用双指针方法找到倒数第K个节点。

1. #include <iostream>
   
2. #include <sstream>
   
3. #include <vector>
   
4. 
   
5. struct ListNode {
   
6.     int value;
   
7.     ListNode* next;
   
8.     ListNode(int val) : value(val), next(nullptr) {}
   
9. };
   
10. 
    
11. ListNode* createLinkedList(const std::vector<int>& values) {
    
12.     ListNode* head = nullptr;
    
13.     ListNode* tail = nullptr;
    
14.     for (int value : values) {
    
15.         ListNode* newNode = new ListNode(value);
    
16.         if (!head) {
    
17.             head = newNode;
    
18.         } else {
    
19.             tail->next = newNode;
    
20.         }
    
21.         tail = newNode;
    
22.     }
    
23.     return head;
    
24. }
    
25. 
    
26. void findKthFromEnd(ListNode* head, int k) {
    
27.     ListNode* first = head;
    
28.     ListNode* second = head;
    
29. 
    
30.     for (int i = 0; i < k; ++i) {
    
31.         if (!first) {
    
32.             std::cout << "Not Found" << std::endl;
    
33.             return;
    
34.         }
    
35.         first = first->next;
    
36.     }
    
37. 
    
38.     while (first) {
    
39.         first = first->next;
    
40.         second = second->next;
    
41.     }
    
42. 
    
43.     if (second) {
    
44.         std::cout << second->value << std::endl;
    
45.     } else {
    
46.         std::cout << "Not Found" << std::endl;
    
47.     }
    
48. }
    
49. 
    
50. int main() {
    
51.     std::string line;
    
52.     std::getline(std::cin, line);
    
53.     std::istringstream iss(line);
    
54.    
    
55.     int k;
    
56.     iss >> k;
    
57. 
    
58.     std::vector<int> values;
    
59.     int num;
    
60.     while (iss >> num) {
    
61.         values.push_back(num);
    
62.     }
    
63. 
    
64.     ListNode* head = createLinkedList(values);
    
65.     findKthFromEnd(head, k);
    
66. 
    
67.     return 0;
    
68. }

复制代码

### 代码解释
- **ListNode结构体**: 表示链表节点，包含整数值和一个指向下一个节点的指针。
- **createLinkedList函数**: 根据输入的整数数组创建链表。
- **findKthFromEnd函数**: 使用双指针方法找到倒数第K个节点。
  - 第一个指针先移动K步，然后两个指针同时移动，直到第一个指针到达末尾。
  - 此时，第二个指针所指即为倒数第K个节点。
- **main函数**: 处理输入，创建链表并调用查找函数。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。