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);}}

运行结果：