pat乙级链表问题

链表题目：一开始以为要按照链表那样一个一个搞，看完这个后思路清晰：1025链表一连a三题链表题。在输入完链表之后，遍历链表使用另一个数组(可以是指针数组也可以是节点数组)记录下该节点的地址或者将节点的顺序调对，并且记录有多少个节点(加个变量记录就行，还可以用来作为变化的数组下标)，读到-1停止。然后就进行对应的操作输出就行了，
以下代码来自柳婼和上面那个链接
1025:反转链表

	#include <iostream>  
	#include <algorithm>  
	using namespace std;  
	int main() {  
		int first, k, n, temp;  
		cin >> first >> n >> k;  
		int data[100005], next[100005], list[100005];  
		for (int i = 0; i < n; i++) {  
			cin >> temp;  
			cin >> data[temp] >> next[temp];  
			}  
		int sum = 0;//不⼀定所有的输⼊的结点都是有⽤的，加个计数器  
		while (first != -1) {  
			list[sum++] = first;  
			first = next[first];  
			}  
		for (int i = 0; i < (sum - sum % k); i += k)  
			reverse(begin(list) + i, begin(list) + i + k);  
		for (int i = 0; i < sum - 1; i++)
			printf("%05d %d %05d\n", list[i], data[list[i]], list[i + 1]);  
			printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);  
		return 0;  
	}
	#include<iostream>
	#include<algorithm>
	using namespace std;
	struct List
	{
		int id;
		int date;
		int next;
	};
	int main()
	{
		struct List p[100000+10];//链表结构体 
		struct List *q[100000+10];//存放链表结构体地址的数组
		int first,num,ty;
		cin>>first>>num>>ty;
		int ID,Date,NEXT;//暂时存放 
		for (int i = 0; i < num; i++) //读数据 
		{
			cin>>ID>>Date>>NEXT;
			p[ID].date=Date;
			p[ID].next=NEXT; 
			p[ID].id=ID;
		 }
		int tk=0; 
		for(int i=first;i!=-1;i=p[i].next)//将数据按顺序存放到指针数组q中 
		{
			q[tk++]=&p[i];
		 } 
		for(int i=tk,j=0;i/ty!=0;i-=ty,j+=ty)
		{
			reverse(q+j,q+j+ty);//逆序指针数组  原来数组存放的链表地址进行逆序 
		}
		for( int i=0;i<tk-1;i++)
		{
			printf("%05d %d %05d\n",q[i]->id,q[i]->date,q[i+1]->id);
		}
		printf("%05d %d -1",q[tk-1]->id,q[tk-1]->date);
		return 0;
	}

1075:链表元素分类

		将结点⽤list[10000]保存， list为node类型， node中保存结点的值value和它的next地址。 list的下标就是结点的地址。将<0、 0～k、 >k三部分的结点地址分别保存在v[0]、 v[1]、 v[2]中，最后将vector中的值依次输出即可  .即只遍历一次，减少遍历次数
		#include <iostream>  
		#include <vector>  
		using namespace std;  
		struct node {  
		int data, next;  
		}list[100000];  
		vector<int> v[3];  
		int main() {  
			int start, n, k, a;  
			scanf("%d%d%d", &start, &n, &k);  
			for (int i = 0; i < n; i++) {  
				scanf("%d", &a);  
				scanf("%d%d", &list[a].data, &list[a].next);  
				}  
			int p = start;  
			while(p != -1) {  
				int data = list[p].data;  
				if (data < 0)  
				v[0].push_back(p);  
				else if (data >= 0 && data <= k)  
				v[1].push_back(p);  
				else  
				v[2].push_back(p);  
				p = list[p].next;  
				}  
			int flag = 0;  
			for (int i = 0; i < 3; i++) {  
				for (int j = 0; j < v[i].size(); j++) {  
					if (flag == 0) {  
						printf("%05d %d ", v[i][j], list[v[i][j]].data);  
						flag = 1;  
						} 
					else {  
					printf("%05d\n%05d %d ", v[i][j], v[i][j], list[v[i][j]].data);  
					}  
				}  
			}  
			printf("-1");  
			return 0;  
		}

1105：链表合并：⽤vector L1、 L2存储题⽬中给定的两个链表， vector ans保存合并后的链表。将较⻓的⼀个链表存储在L1中，如果原本L1较短，则将L1与L2⽤swap函数互相置换~在链表合并的过程中， i从0开始，将L1中每个结点添加到ans中，如果当前i是奇数（i & 1不等于0）就把L2的⼀个结点添加到ans中，直到L2中没有剩余元素,反复，我是遍历了两遍，然后如果大小区分就swap首地址。

#include <iostream>  
#include <vector>  
using namespace std;  
struct node {  
int data, next;  
}A[100000];  
vector<int> L1, L2, ans;  
int sa, sb, n, a, ta, tb, c;  
int main() {  
	cin >> sa >> sb >> n;  
	for (int i = 0; i < n; i++) {  
		cin >> a >> A[a].data >> A[a].next;  
	}  
	ta = sa;  
	while (ta != -1) {  
		L1.push_back(ta);  
		ta = A[ta].next;  
	}  
	tb = sb;  
	while (tb != -1) {  
		L2.push_back(tb);  
		tb = A[tb].next;  
		}  
	if (L1.size() < L2.size()) swap(L1, L2);  
	for (int i = 0, c = L2.size() - 1; i < L1.size(); i++) {  
		ans.push_back(L1[i]);  
		if (i & 1 && c >= 0) ans.push_back(L2[c--]);  
		}  
		for (int i = 1; i < ans.size(); i++) {  
		printf("%05d %d %05d\n", ans[i-1], A[ans[i-1]].data, ans[i]);
	}  
	printf("%05d %d -1", ans.back(), A[ans.back()].data);  
	return 0;  
	}