[已解决]输出单链表倒数第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个节点。

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

跳转到最佳答案楼层

FishC

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