求线性表的倒数第K项 (数组、头插法、尾插法)

2025/4/18 9:53:02 来源：https://blog.csdn.net/MxDxhang/article/details/147070810 浏览: 次关键词：求线性表的倒数第K项 (数组、头插法、尾插法)

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

输入格式:

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

输出格式:

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

输入样例:

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

题目解析：

首先看到这道题目，作为一个线性表，我们要知道，典型的线性表有两种结构，分别是顺序表，和链表，我们就用这两种表，完成这一道题目

顺序表实现：

所谓顺序表，就是我们熟知的数组，这一道题目，他要求一段序列中的倒数第k个序列，那我们就只需要开一个vector数组，然后最后输出就好，非常的简单

//数组
vector<int > a;int x;while(cin>>x&&x>-1){a.push_back(x);}if(n>a.size()||n<1) cout<<"NULL";else  cout<<a[a.size()-n];
}

链表实现：

链表的初始化中，有两种非常典型的方法，分别是头插法和尾插法，那我们就带大家复习一个头插法和尾插法

尾插法：

尾插法，就是把给定的一段序列，把这段序列按照顺序依次插入链表当中，就是每次把要插入的内容插入链表的尾部，但是这道题目当中，我们为了输出倒数的元素，我们就可以设置一个pre指针指向前一个元素

①：初始化要插入的节点p

②：把p插入到链的尾（r->next = p），p的pre指向p（p->pre = r

③：把链的尾调整到p （r=p）

过程大致如下：

代码实现：

//尾插法node *head = new node;head->next = NULL;int cnt = 0;head->pre = NULL;node *r = head,*p;int x;while(cin>>x&&x!=-1){p = new node;p->data = x;p->pre = r;p->next = NULL;r->next = p;r = p;cnt++;}

插入的结束之后，我们在插入的过程中使用了一个cnt来判断链表中的有效元素，来判断要输出的内容是否合法。假设输出合法，因为这时候我们需要输出倒数第n个元素，因为时候我们的r或者p指针指向的是链表当中尾部，我们就只要需要利用p（r）的pre指针往回遍历即可

if(n>cnt||n<=0) cout<<"NULL";else {for(int i = 1;i<n;i++){p = p->pre;}cout<<p->data;}

头插法：

头插法，就是把给的一段序列，按照这一段序列的逆序，插入链表当中，就是把这一段序列，每一个元素插入的时候都都是他的的头部元素

①：初始化要插入的节点p

②：把p的next指向头部元素（p->next = r）

③：把头部元素修改为p（r=p）

④：把p插入头结点之后（head->next = p）

代码实现：

//头插法  int x;node *p,*r;r = NULL;while(cin>>x&&x>=-0) {p = new node;p->data = x;p->next = r;r= p;head->next = r;cnt++;}

插入的结束之后，这时候我们只需要正向遍历，就可以找到我们想找到原来序列的倒数第n个元素

    if(n>cnt||n<=0) cout<<"NULL";else {for(int i = 1;i<n;i++) r = r->next;cout<<r->data;}

全部代码实现：

#include<bits/stdc++.h>
using namespace std;
typedef struct node{int data;struct node *next,*pre;
}node;
int main()
{int n;cin>>n;node *head = new node;head->next = NULL;int cnt = 0;head->pre = NULL;node *r = head,*p;int x;while(cin>>x&&x>=0){p = new node;p->data = x;p->pre = r;p->next = NULL;r->next = p;r = p;cnt++;}if(n>cnt||n<=0) cout<<"NULL";else {for(int i = 1;i<n;i++){p = p->pre;}cout<<p->data;}
}// 头插法  
// 	int x;
// 	node *p,*r;
// 	r = NULL;// 	while(cin>>x&&x>=-0) {// 		p = new node;
// 		p->data = x;
// 		p->next = r;
// 		r= p;
// 		head->next = r;
//         cnt++;
// 	}//   if(n>cnt||n<=0) cout<<"NULL";// else {for(int i = 1;i<n;i++) //    r = r->next;//    cout<<r->data;}// }// //数组：
// vector<int > a;
// 	 int x;
// 	 while(cin>>x&&x>-1){// 	 	a.push_back(x);
// 	 }
//     if(n>a.size()||n<1) cout<<"NULL";
// 	else  cout<<a[a.size()-n];
// }

最后测试点全部通过：