市场调查 网站建设,网站建设制作设计优化,简单的网站建立怎么做,有没有专门做布料的网站写在前面#xff1a; 做题环境如下#xff1a; 题目渠道#xff1a;牛客网 HJ51 输出单向链表中倒数第k个结点 华为机试题 编程语言#xff1a;C 一、题目描述
描述 输入一个单向链表#xff0c;输出该链表中倒数第k个结点#xff0c;链表的倒数第1个结点为链表的尾指针…写在前面 做题环境如下 题目渠道牛客网 HJ51 输出单向链表中倒数第k个结点 华为机试题 编程语言C 一、题目描述
描述 输入一个单向链表输出该链表中倒数第k个结点链表的倒数第1个结点为链表的尾指针。
链表结点定义如下
struct ListNode
{int m_nKey;ListNode* m_pNext;
};正常返回倒数第k个结点指针异常返回空指针. 要求 (1)正序构建链表; (2)构建后要忘记链表长度。 数据范围链表长度满足 [1,1000],链表中数据满足 [010000] 输入描述 输入说明 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) {vectorListNode* 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) {vectorListNode* 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{couterrorendl;}
}
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);}}运行结果
