华为机试-输出单向链表中倒数第k个结点（较难）

题目描述

输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。

方法1：

偷懒，vector也可以通过

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int num;
    while(cin>>num){
        vector<int> temp;
        for(int i=0;i<num;i++){
            int a;cin>>a;
            temp.push_back(a);
        }
        int k;
        cin>>k;
        cout<<temp[num-k]<<endl;
    }

}

方法2：

自己写链表，是顺序尾插入的。然后输出第 num-k 个数字。
注意判断目标位置k是否超过num或者<=0(!!!!!!!!!!!)

#include<iostream>
#include<list>
struct ListNode
{
    int m_nKey;
    ListNode* m_pNext;
    ListNode(int x):m_nKey(x),m_pNext(nullptr){};//记住写法
};
using namespace std;
int main(){
    int num;
    while(cin>>num){
        ListNode* head=new ListNode(-1);
        ListNode* p=head;
        for(int i=0;i<num;i++){
            int a;cin>>a;
            ListNode* q=new ListNode(a);
            q->m_pNext=nullptr;
            p->m_pNext=q;
            p=q;
        }
        int k;cin>>k;
        if(k<=0||k>num) {cout<<0<<endl;continue;}//注意判断为0和超界的情况，否则报段错误
        for(int i=0;i<num-k+1;i++){
            head=head->m_pNext;
        }
        cout<<head->m_nKey<<endl;
    }

}