PAT链表专题

关于PAT甲级的链表问题，主要内容 就是”建立链表“

所以第一步学会模拟链表，pat又不卡时间，这里用vector + 结构体，更简洁

模拟链表的普遍代码

const int maxn = 1e6+10;

struct node{

	int address;

	int next;

	char key;

}nod[maxn];

int head1,n;

vector<node> list1;

cin>>head1>>n;

for(int i=1;i<=n;i++) {

    int address,next;

    char key;

    cin>>address>>key>>next;

    nod[address].address = address;//重点1

    nod[address].key = key;

    nod[address].next = next;

}

for(head1; head1 != -1; head1 = nod[head1].next){ //重点2

    list1.push_back(nod[head1]);

}

学会模拟链表之后，PAT甲级的链表题就都能做了，万变不离其宗，

基本就是，建立链表、按照题意操作链表（链表合并、去重、反转...）、注意判断链表边界（链表有效长度）、输入输出( %05d 来输出地址)

2019秋季PAT 7-2

#include<bits/stdc++.h>

using namespace std;

const int maxn = 100001;

int ad1,ad2,n;

int head1,head2 = 0;

int len1 = 0,len2 = 0;

struct node{

	int add,next,key;

}nod[maxn];

vector<node> list1;

vector<node> list2;

vector<node> res;

int main(){

	cin>>head1>>head2>>n;

	for(int i=1;i<=n;i++){

		int add,next,key;

		cin>>add>>key>>next;

		nod[add].add = add;

		nod[add].next = next;

		nod[add].key = key;

	}

    for (int p = head1; p != -1; p = nod[p].next)

        list1.push_back(nod[p]);

	for(int p = head2;p!=-1;p = nod[p].next)

		list2.push_back(nod[p]);

	len1 = list1.size()-1;

	len2 = list2.size()-1;

	if(len1 >= 2*len2){

		int p = 0,q = len2;

		while(q >= 0){

			res.push_back(list1[p++]);

			res.push_back(list1[p++]);

			res.push_back(list2[len2--]);

		}

		while(p <= len1){

			res.push_back(list1[p++]);

		}

		for(int i=0;i<res.size();i++){

			if(i != res.size() - 1){

				res[i].next = res[i+1].add;

			}

		}

	}else{

		int p = len1,q = 0;

		while(p >= 0){

			res.push_back(list2[q++]);

			res.push_back(list2[q++]);

			res.push_back(list1[p--]);

		}

		while(q<=len2){

			res.push_back(list2[q++]);

		}

		for(int i=0;i<res.size();i++){

			if(i != res.size() - 1){

				res[i].next = res[i+1].add;

			}

		}

	}

	for(int i=0;i<res.size();i++){

		if(i == res.size()-1) printf("%05d %d -1\n",res[i].add,res[i].key);

		else printf("%05d %d %05d\n",res[i].add,res[i].key,res[i].next);

	}

	return 0;

}

PTA1032

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+10;

struct node{

	int address;

	int next;

	char key;

}nod[maxn];

int head1,head2,n;

bool use[maxn];

vector<node> list1,list2;

int main(){

	cin>>head1>>head2>>n;

	for(int i=1;i<=n;i++) {

		int address,next;

		char key;

		cin>>address>>key>>next;

		nod[address].address = address;

		nod[address].key = key;

		nod[address].next = next;

	}

	for(head1; head1 != -1; head1 = nod[head1].next){

		list1.push_back(nod[head1]);

		use[head1] = true;

	}

	for(head2; head2 != -1; head2 = nod[head2].next){

		if(use[head2]){

			printf("%05d\n",head2);

			return 0;

		}

	}

	cout<<"-1"<<endl;

	return 0;

}

PTA1052

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+100;

struct node{

	int address;

	int key;

	int next;

	bool flag;

}nod[100010];

vector<node> list1;

int n;

int head;

bool cmp(node a,node b){

	return a.key < b.key;

}

int main(){

	cin>>n>>head;

	for(int i=1;i<=n;i++){

		int address,key,next;

		cin>>address>>key>>next;

		nod[address].address = address;

		nod[address].key = key;

		nod[address].next = next;

		nod[address].flag = true;

	}

	int m = 0;

	for(;head!=-1;head = nod[head].next){

		nod[head].flag = true;

		list1.push_back(nod[head]);

		m++;

	}

	if(m == 0){ //判边界 否则段错误

		printf("0 -1\n");

		return 0;

	}

	sort(list1.begin(),list1.end(),cmp);

	for(int i=0;i<m-1;i++){

		list1[i].next = list1[i+1].address;

	}

	cout<<m<<" ";

	printf("%05d\n",list1[0].address);

	for(int i=0;i<m-1;i++){

		printf("%05d %d %05d\n",list1[i].address,list1[i].key,list1[i].next);

	}

	printf("%05d %d -1\n",list1[m-1].address,list1[m-1].key);

	return 0;

}

PTA1074

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

/*

题目意思是 k个元素间换一下

*/

struct node{

	int address;

	int key;

	int next;

}nod[maxn];

vector<node>list1,list2;

int head,n,k;

void print(){

	for(int i=0;i<n-1;i++){

		printf("%05d %d %05d\n",list2[i].address,list2[i].key,list2[i].next);

	}

	printf("%05d %d -1\n",list2[n-1].address,list2[n-1].key);

}

int main(){

	cin>>head>>n>>k;

	for(int i=0;i<n;i++){

		int add,key,next;

		cin>>add>>key>>next;

		nod[add].address = add;

		nod[add].key = key;

		nod[add].next = next;

	}

	for(;head!=-1;head=nod[head].next)

		list1.push_back(nod[head]);

	n = list1.size(); //原来的n不一定是新链表的长度 可能输入数据有无效结点 

	int pos = 0;

	while(pos + k - 1 < n){ //这里注意 下标 每pos~pos+k-1为一组

		for(int i = pos+k-1;i>=pos;i--){ //倒序存进list2

			list2.push_back(list1[i]);

		}

		pos+=k;

	}

	if(pos < n){ //剩下的没有凑够k个就 直接存入链表list2

		for(int i=pos;i<n;i++){//正序存进list2

			list2.push_back(list1[i]);

		}

	}

	for(int i=0;i<n-1;i++){ //更新next地址

		list2[i].next = list2[i+1].address;

	}

	list2[n-1].next = -1;

	print();

	return 0;

} 

/*

00100 4 2

00000 4 -1

00100 1 12309

33218 3 00000

12309 2 33218

*/

PTA1097

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int head,n;

struct node{

	int address;

	int key;

	int next;

}nod[maxn]; 

bool vis[maxn];

vector<node> list1,list2;

int main(){

	cin>>head>>n;

	for(int i = 0;i < n;i++){

		int add,key,next;

		cin>>add>>key>>next;

		nod[add].address = add;

		nod[add].key = key;

		nod[add].next = next;

	}

	for(;head!=-1;head = nod[head].next){

		if(!vis[abs(nod[head].key)]){

			vis[abs(nod[head].key)] = true;

			list1.push_back(nod[head]);

		}else{

			list2.push_back(nod[head]);

		}

	}

	n = list1.size();

	if(n != 0){

		for(int i=0;i<n-1;i++){

			printf("%05d %d %05d\n",list1[i].address,list1[i].key,list1[i+1].address);

		}

		printf("%05d %d -1\n",list1[n-1].address,list1[n-1].key);

	}

	int m = list2.size();

	if(m != 0){

		for(int i=0;i<m-1;i++){

			printf("%05d %d %05d\n",list2[i].address,list2[i].key,list2[i+1].address);

		}

		printf("%05d %d -1\n",list2[m-1].address,list2[m-1].key);

	}

	return 0;

}