HJ51 输出单向链表中倒数第k个结点-Toy模板网

这篇具有很好参考价值的文章主要介绍了HJ51 输出单向链表中倒数第k个结点。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

写在前面：

做题环境如下：
题目渠道：牛客网 HJ51 输出单向链表中倒数第k个结点华为机试题
编程语言：C++

一、题目描述

描述
输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。

链表结点定义如下：

struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
};

正常返回倒数第k个结点指针，异常返回空指针.
要求：
(1)正序构建链表;
(2)构建后要忘记链表长度。
数据范围：链表长度满足 [1,1000],链表中数据满足 [0，10000]
输入描述：
输入说明

1 输入链表结点个数
2 输入链表的值
3 输入k的值

输出描述：

输出一个整数

示例1
输入：

8
1 2 3 4 5 6 7 8
4

输出

5

说明：本题有多组样例输入。

二、题目分析&解题思路

2.1 处理好输入

牛客网与leetCode 不同，牛客需要自己处理好输入，构建输入环境，而这里题目给出了单链表节点类型的写法，那么如果再使用容器 list 那么就有点没意思了，因此需要自己逐个添加节点，设置节点值、下一个节点指针等，这里需要注意 本题有多组样例输入 那么说明我们需要把我们的代码写在一个 while 循环里，供测试用例循环输入：

    int number;
    while (cin >> number) {//循环测试用例输入
        ListNode* head = new ListNode();//头节点
        ListNode* next = new ListNode();
        bool bflag = true;
        while (number > 0) {
            int val;
            cin >> val;
            ListNode* nodeTemp = new ListNode();//构建每一个节点
            nodeTemp->m_nKey = val;
            nodeTemp->m_pNext = nullptr;
            if (bflag) {
                head = nodeTemp;//先将头节点保存
                next = head;
                bflag = false;
            } else {
                next->m_pNext = nodeTemp;//逐个链接起来
                next = next->m_pNext;
            }
            --number;
        }
        int key;
        cin >> key;
        getReversKeyNode(head, key);
    }

2.2 处理输出

也就是实现将倒数第 K 个节点值输出，这里直接遍历所有的节点，保存到一个 vector 中，直接根据K 计算出节点下标，输出即可，代码复杂度为 O(n)

void getReversKeyNode(ListNode* head, int key) {

    vector<ListNode*> vctTemp;
    while (head != nullptr) {
        vctTemp.push_back(head);
        head = head->m_pNext;
    }
    if (vctTemp.size() > 0) {
        if (key <= vctTemp.size() && key >= 0 ) {
            cout << vctTemp[vctTemp.size() - key]->m_nKey << endl;//计算下标
        } else {
            cout << "error" << endl;
        }
    }
}

三、代码实现

#include <iostream>
#include <vector>
using namespace std;
typedef struct ListNode {
    int m_nKey;
    ListNode* m_pNext;
} ListNode;
void getReversKeyNode(ListNode* head, int key) {

    vector<ListNode*> vctTemp;
    while (head != nullptr) {
        vctTemp.push_back(head);
        head = head->m_pNext;
    }
    if (vctTemp.size() > 0) {
        if (key <= vctTemp.size() && key >= 0 ) {
            cout << vctTemp[vctTemp.size() - key]->m_nKey << endl;//计算下标
        } else {
            cout << "error" << endl;
        }
    }
    else
    {
    	cout<<"error<<endl;
    }
}
int main() {
    int number;
    while (cin >> number) {//循环用例输入
        ListNode* head = new ListNode();//头节点
        ListNode* next = new ListNode();
        bool bflag = true;
        while (number > 0) {
            int val;
            cin >> val;
            ListNode* nodeTemp = new ListNode();//构建每一个节点
            nodeTemp->m_nKey = val;
            nodeTemp->m_pNext = nullptr;
            if (bflag) {
                head = nodeTemp;//设置头节点
                next = head;
                bflag = false;
            } else {
                next->m_pNext = nodeTemp;//链接每一个节点
                next = next->m_pNext;
            }
            --number;
        }
        int key;
        cin >> key;
        getReversKeyNode(head, key);
    }

}