输出单链表倒数第K个结点值
【问题描述】输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第1个节点。
【输入形式】
输入第一位为K值，其后接一串以空格分隔的整型值。
【输出形式】
输出为倒数第K个结点的值，若无，则输出Not Found
【样例输入】
3 13 45 54 32 1 4 98 2
【样例输出】
4
【样例说明】
K值为3，则输出链表倒数第3个结点的值，为4；数据输入间以空格隔开
【评分标准】
本题要综合输出正确性及使用的数据结构。需由输入数据构建单链表。不使用链表的将不得分。
这题用C++怎么做 我们可以使用C++编写一个程序，通过构建一个单向链表获取倒数第K个节点的值。以下是实现步骤和代码示例：
1. 定义链表节点的结构。
2. 创建链表并读取输入值。
3. 使用双指针方法找到倒数第K个节点。
#include <iostream>
#include <sstream>
#include <vector>
struct ListNode {
int value;
ListNode* next;
ListNode(int val) : value(val), next(nullptr) {}
};
ListNode* createLinkedList(const std::vector<int>& values) {
ListNode* head = nullptr;
ListNode* tail = nullptr;
for (int value : values) {
ListNode* newNode = new ListNode(value);
if (!head) {
head = newNode;
} else {
tail->next = newNode;
}
tail = newNode;
}
return head;
}
void findKthFromEnd(ListNode* head, int k) {
ListNode* first = head;
ListNode* second = head;
for (int i = 0; i < k; ++i) {
if (!first) {
std::cout << "Not Found" << std::endl;
return;
}
first = first->next;
}
while (first) {
first = first->next;
second = second->next;
}
if (second) {
std::cout << second->value << std::endl;
} else {
std::cout << "Not Found" << std::endl;
}
}
int main() {
std::string line;
std::getline(std::cin, line);
std::istringstream iss(line);
int k;
iss >> k;
std::vector<int> values;
int num;
while (iss >> num) {
values.push_back(num);
}
ListNode* head = createLinkedList(values);
findKthFromEnd(head, k);
return 0;
}
### 代码解释
- **ListNode结构体**: 表示链表节点，包含整数值和一个指向下一个节点的指针。
- **createLinkedList函数**: 根据输入的整数数组创建链表。
- **findKthFromEnd函数**: 使用双指针方法找到倒数第K个节点。
- 第一个指针先移动K步，然后两个指针同时移动，直到第一个指针到达末尾。
- 此时，第二个指针所指即为倒数第K个节点。
- **main函数**: 处理输入，创建链表并调用查找函数。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]