对PAT考试中的链表类题进行总结。 🙈
PAT上考查链表的题挺多，这篇介绍链表的一种解题思路，方法不是最好的，但理解跟操作还是比较容易的。
解题套路：
1.输入的时候用一个结构体把数据存起来（结构的作用是记录数据data跟下一个地址，方便连起来），输入的地址作为结构体的下标。
2.通过while循环把链表的地址按顺序存到数组a中。
3.根据题目的要求（排序的规则），把a数组里的地址按顺序排到另一个数组b中。
4.输出即可。
B1025/A1074. 反转链表 (25分)
给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。
输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤10^5)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。
接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
#include<stdio.h>
struct node{
int data; //数据
int next; //下一个结点的地址
}p[100005];
int main(){
int N,K,first,ad;
int lb=0,l=0,i;
int b[100005],ans[100005];
scanf("%d %d %d",&first,&N,&K);
for(i=0;i<N;i++){
scanf("%d",&ad);
scanf("%d %d",&p[ad].data,&p[ad].next);
}
while(first!=-1){//给链表正常排序 （这个步骤在排序的过程中，也把输入中的垃圾结点过滤掉了（输入的结点不一定在链表上））
b[lb]=first;
first=p[first].next; //地址作为下标后，通过地址就可以找到下一个结点的地址了
lb++;
}
int y=lb%K; // y是余数，最后存
for(i=0;i<lb-y;i++){
if((i+1)%K==0){ //如果满足K个，就将反转
for(int j=i;j>=i+1-K;j--){
ans[l]=b[j];l++;
}
}
}
if(y){ //如果余数不为0，最后部分正序补上
for(i=lb-y;i<lb;i++){
ans[l]=b[i];l++;
}
}
for(i=0;i<l;i++){ //输出的格式是address data next
if(i!=l-1)printf("%05d %d %05d\n",ans[i],p[ans[i]].data,ans[i+1]); //这里ans[i]为当前结点的地址 p[ans[i]].data就是地址指向的结点的数据 ans[i+1]为下一个地址
else printf("%05d %d -1\n",ans[i],p[ans[i]].data); //因为最后一个结点的下一个地址是NULL，所以分开输出
}
return 0;
}
1075 链表元素分类 (25分)
给定一个单链表，请编写程序将链表元素进行分类排列，使得所有负值元素都排在非负值元素的前面，而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如：给定链表为 18→7→-4→0→5→-6→10→11→-2，K 为 10，则输出应该为 -4→-6→-2→7→0→5→10→18→11。
输入格式：
每个输入包含一个测试用例。每个测试用例第 1 行给出：第 1 个结点的地址；结点总个数，即正整数N (≤10^5 )；以及正整数K (≤10^3 )。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。
接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址；Data 是该结点保存的数据，为 [−10^5 ,10^5 ] 区间内的整数；Next 是下一结点的地址。题目保证给出的链表不为空。
输出格式：
对每个测试用例，按链表从头到尾的顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 9 10
23333 10 27777
00000 0 99999
00100 18 12309
68237 -6 23333
33218 -4 00000
48652 -2 -1
99999 5 68237
27777 11 48652
12309 7 33218
输出样例：
33218 -4 68237
68237 -6 48652
48652 -2 12309
12309 7 00000
00000 0 99999
99999 5 23333
23333 10 00100
00100 18 27777
27777 11 -1
这题有点麻烦，要求有点多，我的方法比较直接（笨）。题目要求：负值 排前面，其次 [0,K],最后排 >K 的元素。所以直接用3个组数分别把三个区间的元素挑选出来，再按顺序合并到一个数组，最后输出就可以了。
#include<iostream>
#include<cstdio>
using namespace std;
struct node{
int data;
int next;
}p[100005];
int main(){//f存负数，kl存[0,K]的数，kr存大于K的数，ans存结果
int N,K,temp,a[100004],f[100004],kl[100004],kr[100004],ans[100004],first;
int i,l=0,la=0,lr=0,lk=0,lf=0;
cin>>first>>N>>K;
for(i=0;i<N;i++){
cin>>temp;
cin>>p[temp].data>>p[temp].next;
}
while(first!=-1){
a[la++]=first;
first=p[first].next;
}//下面为元素分类
for(i=0;i<la;i++){
if(p[a[i]].data<0) f[lf++]=a[i]; //负数
else if(p[a[i]].data>=0&&p[a[i]].data<=K) kl[lk++]=a[i]; //0~K的数
else kr[lr++]=a[i]; // 大于K的数
}//下面按顺序合并
for(i=0;i<lf;i++) ans[l++]=f[i]; //负数
for(i=0;i<lk;i++) ans[l++]=kl[i]; //0~K的数
for(i=0;i<lr;i++) ans[l++]=kr[i]; // 大于K的数
for(i=0;i<l;i++){
if(i!=l-1)printf("%05d %d %05d\n",ans[i],p[ans[i]].data,ans[i+1]);
else printf("%05d %d -1\n",ans[i],p[ans[i]].data);
}
return 0;
}
L2-002 链表去重 (25分)
给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值 K，只有第一个绝对值等于 K 的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为 21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。
输入格式：
输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤10^5，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 −1 来表示。
随后 N 行，每行按以下格式描述一个结点：
地址 键值 下一个结点
其中地址是该结点的地址，键值是绝对值不超过10^4 的整数，下一个结点是下个结点的地址。
输出格式：
首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。
输入样例：
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
输出样例：
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
解题思路：这道题的要求是去重，而且输出为两个链表，所以我们需要两个数组存去重后的分成的两个链表的地址；而且只保留第一个绝对值的数，后面重复的就放到链表b中。
#include<iostream>
#include<unordered_map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
struct node{
int next;
int data;
}p[100005],q[100005];
unordered_map<int,int>mp;//不自动排序，也可以用上面的q来查询是不是第一个出现的元素（绝对值）
vector<int>a,b,c;
int main(){
int N,i,temp,first;
cin>>first>>N;
for(i=0;i<N;i++) cin>>temp>>p[temp].data>>p[temp].next;//temp作为下标
while(first!=-1){ //链表排序且去除垃圾结点
a.push_back(first);
first=p[first].next;
}
for(i=0;i<a.size();i++){
int x=fabs(p[a[i]].data);
if(!mp[x]){ //如果mp不为空说明该结点元素的绝对值是第一次出现
b.push_back(a[i]);
mp[x]=1; //标明x这个元素已有了
}
else c.push_back(a[i]); //c存取绝对值后重复的元素
}
for(i=0;i<b.size();i++){ //链b输出
if(i!=b.size()-1) printf("%05d %d %05d\n",b[i],p[b[i]].data,b[i+1]);
else printf("%05d %d %d\n",b[i],p[b[i]].data,-1);
}
for(i=0;i<c.size();i++){ //链c输出
if(i!=c.size()-1) printf("%05d %d %05d\n",c[i],p[c[i]].data,c[i+1]);
else printf("%05d %d %d\n",c[i],p[c[i]].data,-1);
}
return 0;
}
L2-022 重排链表 (25分)
给定一个单链表 L1 →L2 →⋯→Ln−1→Ln，请编写程序将链表重新排列为 Ln →L1→Ln−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。
输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤10^5)。结点的地址是5位非负整数，NULL地址用−1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址；Data是该结点保存的数据，为不超过10^5的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出格式：
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1
这题排序很容易实现，先取尾部元素，再取头部元素就可以了。
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
struct node{
int next;
int data;
}p[100005];
int main(){
int N,i,j,temp,first;
vector<int>a,ans;
cin>>first>>N;
for(i=0;i<N;i++){
cin>>temp; //先输入temp
cin>>p[temp].data>>p[temp].next;
// cin>>temp>>p[temp].data>>p[temp].next; 写成一行，有问题，可能是temp还没赋上值，所以后面两个输入失败
}
while(first!=-1){ //排序+过滤
a.push_back(first);
first=p[first].next;
}
for(i=0,j=a.size()-1;i!=a.size()/2;i++,j--){
ans.push_back(a[j]); //先加尾部元素
ans.push_back(a[i]); //后加头部元素
}
if(a.size()%2) ans.push_back(a[i]); //上面循环只对偶数个有效，当a.size()%2!=0时，把中间的元素加上
for(i=0;i<ans.size();i++){ //输出
if(i!=ans.size()-1) printf("%05d %d %05d\n",ans[i],p[ans[i]].data,ans[i+1]);
else printf("%05d %d %d\n",ans[i],p[ans[i]].data,-1);
}
return 0;
}
7-5 区块反转 (25分)
给定一个单链表 L，我们将每 K 个结点看成一个区块（链表最后若不足 K 个结点，也看成一个区块），请编写程序将 L 中所有区块的链接反转。例如：给定 L 为 1→2→3→4→5→6→7→8，K 为 3，则输出应该为 7→8→4→5→6→1→2→3。
输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤10^5)、以及正整数 K (≤N)，即区块的大小。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。
接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218
输出样例：
71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1
这题是PAT冬季的最后一道题，当时只拿了24分，卡在一个点上（委屈.png) 一样，按套路来救行了，前面的基本不变，只是题目要求的排序不同而已。 题目要求：以K为一个区块反转链表，最后不足K也要反转
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
struct node{
int next;
int data;
}p[100005];
int main(){
int first,N,K,temp,i;
vector<int>ad;
cin>>first>>N>>K;
for(i=0;i<N;i++){
cin>>temp;
cin>>p[temp].data>>p[temp].next;
}
temp=first;
while(temp!=-1){
ad.push_back(temp);
temp=p[temp].next;
}
for(i=1;i<=ad.size()/K;i++){ //ad.size()/K表示K个区块，即反转的次数
reverse(ad.begin()+K*(i-1),ad.begin()+K*i);//这需要找出反转的规律然后用公式来代替，从第一个元素开始到K个元素，如当i=1,K=3时，反转区间为（ad.begin(),ad.begin+3),即第一个元素到第三个元素反转，后面以此类推
}
if(ad.size()%K!=0){ //如果有余数，则后面还有不满足K个的区块，也要反转
reverse(ad.end()-(ad.size()%K),ad.end());
}
for(i=ad.size()-1;i>=0;i--){ //最后逆序输出就跟样例一样了
if(i)printf("%05d %d %05d\n",ad[i],p[ad[i]].data,ad[i-1]);
else printf("%05d %d -1\n",ad[i],p[ad[i]].data);
}//不过可能是因为我逆序输出，所以这题当K=1时，我的代码逆序输出，但答案好像是正序输出的，所以可能我丢的一分就在这。。。(后知后觉的蠢- -)
return 0;
}
1032 Sharing (25分)
To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, loading and being are stored as showed in Figure 1.
图略
You are supposed to find the starting position of the common suffix (e.g. the position of i in Figure 1).
Input Specification:
Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (≤10^5), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by −1.
Then N lines follow, each describes a node in the format:
Address Data Next
whereAddress is the position of the node, Data is the letter contained by this node which is an English letter chosen from { a-z, A-Z }, and Next is the position of the next node.
Output Specification:
For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output -1 instead.
Sample Input 1:
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010
Sample Output 1:
67890
Sample Input 2:
00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1
Sample Output 2:
-1
找到链表La、Lb第一个公共结点，找不到输出-1。
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<cmath>
#include<set>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
int next;
char data;
}p[100005];
vector<int>a;
int mpb[100005];
int main(){
int N,ad,fa,fb;
cin>>fa>>fb>>N;
for(int i=0;i<N;i++){
scanf("%d\n",&ad);
scanf("%c %d",&p[ad].data,&p[ad].next);
}
while(fa!=-1){
a.push_back(fa);
fa=p[fa].next;
}
while(fb!=-1){
mpb[fb]=1;
fb=p[fb].next;
}
for(int i=0;i<a.size();i++){
if(mpb[a[i]]){
printf("%05d\n",a[i]);
return 0;
}
}
cout<<-1<<endl;
return 0;
}
A1052 Linked List Sorting (25分)
A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive N (<10^5) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by −1.
Then N lines follow, each describes a node in the format:
Address Key Next
where Address is the address of the node in memory, Key is an integer in [−10^5,10^5], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.
Output Specification:
For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.
Sample Input:
5 00001
11111 100 -1
00001 0 22222
33333 100000 11111
12345 -1 33333
22222 1000 12345
Sample Output:
5 12345
12345 -1 00001
00001 0 11111
11111 100 22222
22222 1000 33333
33333 100000 -1
结构体存放数据，用sort对存放地址的数组排序
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<unordered_map>
#include<cmath>
#include<set>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
int data,next;
}p[1000005];
int cmp(int x,int y){
return p[x].data<p[y].data; //可以利用结构体对链表地址排序（传入的参数是地址）
}
int main(){
int N,first,ad;
vector<int>ans;
cin>>N>>first;
for(int i=0;i<N;i++){
scanf("%d",&ad);
scanf("%d %d",&p[ad].data,&p[ad].next);
}
while(first!=-1){
ans.push_back(first);
first=p[first].next;
}
sort(ans.begin(),ans.end(),cmp);
if(ans.size())printf("%d %05d\n",ans.size(),ans[0]);
else printf("0 -1"); //漏掉这个最后测试点会不通过
for(int i=0;i<ans.size();i++){
if(i!=ans.size()-1)printf("%05d %d %05d\n",ans[i],p[ans[i]].data,ans[i+1]);
else printf("%05d %d -1\n",ans[i],p[ans[i]].data);
}
return 0;
}
.
.
.
2019年的最后一篇博客，哈~~
2019年12月31日 23:59:27