题解 | #输出单向链表中倒数第k个结点#
输出单向链表中倒数第k个结点
http://www.nowcoder.com/practice/54404a78aec1435a81150f15f899417d
看到题解中有许多做法，但是很多都违背题目本意。
题目考察有：
- 考察参赛者构建链表能力；
- 考察参赛者使用链表的能力。
违背本意的做法有：
- 不构建链表，使用其他容器;
- 倒序构建链表，为查找倒数第k个节点抄近路；
- 记住链表长度n，查找第n-k个节点。
但本题必须要(1)正序构建链表;(2)构建后要忘记链表长度。
这里使用递归查找倒数第k个链表：
#include<iostream>
using namespace std;
struct ListNode{
int m_nKey;
ListNode* m_pNext;
ListNode():m_nKey(0),m_pNext(nullptr){};
ListNode(int x):m_nKey(x),m_pNext(nullptr){};
};
ListNode* getNode(ListNode* node, int& node_num){
if(node==NULL) return NULL;
ListNode* head=getNode(node->m_pNext,node_num);
if(--node_num==0) return node;
else return head;
}
int main(){
int node_num,node;
while(cin>>node_num){
ListNode* head=new ListNode();//正序构建链表
ListNode* pre_head=head;
while(node_num--){
cin>>node;
ListNode* next=new ListNode(node);
head->m_pNext=next;
head=next;
}
cin>>node_num;
ListNode* rec=getNode(pre_head->m_pNext,node_num);//忘记链表长度，递归找到指定节点
if(rec!=NULL) cout<<rec->m_nKey<<endl;
else cout<<"0"<<endl;
}
return 0;
}
投递美团等公司10个岗位 >
Soul一面9人在聊