题解 | #输出单向链表中倒数第k个结点#

看到题解中有许多做法，但是很多都违背题目本意。
题目考察有：

1. 考察参赛者构建链表能力；
2. 考察参赛者使用链表的能力。

违背本意的做法有：

1. 不构建链表，使用其他容器;
2. 倒序构建链表，为查找倒数第k个节点抄近路；
3. 记住链表长度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;
}