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

#include<iostream>
#include<vector>
#include<stack>
using namespace std;

typedef struct ListNode {
    int m_nKey;
    ListNode* n_pNext;
}*LinkNode;

LinkNode creatList(int num,vector<int> value)
{
    LinkNode Head = new ListNode;
    Head->m_nKey=value[0];
    Head->n_pNext=NULL;
    LinkNode p = Head;
    for(int i=1 ; i<num ; i++){
        LinkNode node = new ListNode;
        node->m_nKey=value[i];
        node->n_pNext=NULL;
        p->n_pNext = node ;
        p = node;
    }
    return Head;
}

int main()
{
    LinkNode H;
    int num;
    int k;
    vector<int>value;
    int i=0;
    while(cin>>num){

        value.resize(num);
        for(int i = 0; i<num ; i++){
            cin>>value[i];
        }
        cin >> k ;

        H = creatList(num,value);
        stack<int> mystack;
        LinkNode p = H;
        while(p!=NULL){
            mystack.push(p->m_nKey);
            p = p->n_pNext;
        }
        for(int i=0 ; i<(k-1); i++){
            mystack.pop();
    }
        cout<<mystack.top()<<endl;
    }
    return 0;
}

看了下主要有两种解法，一种是双指针（这确实是个好思路），还有一个是使用递归。

我通过先建了一个stack容器，把正序链表依次入栈，然后出栈对应的个数，本质思想和递归也是一样的。但不知道有没有违背题目的本意，因为我使用了stack容器