1-6 求链式线性表的倒数第K项

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

输入格式:

输入首先给出一个正整数K，随后是若干非负整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。

输出格式:

输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息NULL。

样例">样例">输入样例:

4 1 2 3 4 5 6 7 8 9 0 -1

输出样例:

7

思路：可以用数组模拟链表，头插法的话直接就是第k项。或者用链表的尾插法。

如果不考虑使用链表，那么可以直接按思路走，这边还是给出链表的方法，毕竟为了锻炼！

数组模拟：

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;

ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
const int N = 10000010;
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 将x插到头结点
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}

// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}

// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int n, k;//这是头插法且数组模拟


int main()
{
    IOS;
    cin >> k;
    init();
    
    while(1)
    {
        int x;
        cin >> x;
        if(x >=0) add_to_head(x);
        else break;
    }
   
    
    if(k > idx)
    {
        cout << "NULL" << endl;
        return 0;
    }
    int cnt = 0;
    for (auto it = head; ~it; it = ne[it])
    {
        cnt ++;
        if(cnt == k)    cout << e[it] << endl;
    }
    
    return 0;
}

链表尾插法：

#include<bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define endl '\n'
#define rep(i,a,n) for (int i = a; i < n; i ++ )
#define repn(i,a,n) for (int i = a; i <= n; i ++ )
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
typedef long long ll;
typedef pair<int,int> PII;

ll gcd(ll a,ll b) { return b ? gcd(b,a % b) : a; }
const int mod = 1e9+7;
struct Node
{
    int value;
    Node *next;
}a[100010], *head, *tail;


int main()
{
    IOS;
    int k;
    cin >> k;
    int cnt = 0;
    for (int i = 1; i; i ++ )
    {
        int x;
        cin >> x;
        if(x >= 0)  a[i].value = x, cnt ++;
        else    break;
        if(head == NULL)
        {
            head = tail = &a[i];
        }
        else
        {
            tail->next = &a[i];
            tail = &a[i];
        }
    }
    if(k > cnt) 
    {
        cout << "NULL" << endl;
        return 0;
    }
    else
    {
        int j = 0;
        for (auto it = head; it; it = it->next)
        {
            j ++;
            if(j == cnt - k + 1)    
            {
                cout << it->value << endl;
                return 0;
            }
        }
    }
    
    return 0;
}