题意

读入一个链表

返回其倒数第k个元素

限制，链表长度不大于1000

方法

直接输出

因为数据是我们依次读入的，而不是只获取到链表头，所以我们存储如果按照数组依次存储，直接可以输出倒数第k个，就是下标n-k的输出即可

代码

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i = (a);i<(b);i++)
using namespace std;

struct ListNode {
    int m_nKey;
    ListNode* m_pNext;
} node[1010];

int main(){
    int n;
    while(~scanf("%d",&n)){
        rep(i,0,n){
            scanf("%d",&node[i].m_nKey); // 读入
            node[i].m_pNext = i+1 < n ? &node[i+1] : NULL; // 建立链表
        }
        int k;
        scanf("%d",&k);
        printf("%d\n",node[n-k].m_nKey);
    }
    return 0;
}

复杂度分析

时间复杂度: 耗时主要在读入，时间复杂度$O(n)O(n)$

空间复杂度: 储存了整个链表，空间复杂度$O(n)O(n)$

模拟链表遍历

以样例数据为例

通过itr = itr->m_pNext在链表上进行遍历

通过idx每次减1，直到零来找到n-k下标的结点即可。

代码

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i = (a);i<(b);i++)
using namespace std;

struct ListNode {
    int m_nKey;
    ListNode* m_pNext;
} node[1010];

int main(){
    int n;
    while(~scanf("%d",&n)){
        rep(i,0,n){
            scanf("%d",&node[i].m_nKey); // 读入
            node[i].m_pNext = i+1 < n ? &node[i+1] : NULL; // 建立链表
        }
        int k;
        scanf("%d",&k);
        if(k<=0){
            printf("%d\n",NULL);
            continue;
        }
        int idx = n - k;
        ListNode * itr = node;
        while(idx){
            itr = itr->m_pNext; // 下一个结点
            idx--; // 计数
        }
        printf("%d\n",itr->m_nKey);
    }
    return 0;
}

复杂度分析

时间复杂度: 读入和遍历链表都是$O(n)O(n)$,所以总时间复杂度为$O(n)O(n)$

空间复杂度: 储存了整个链表，空间复杂度$O(n)O(n)$