PAT乙级 链表题-1025、1075、1105、1110
题目：
PAT乙级1025 反转链表
https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805296180871168
PAT乙级1075 链表元素分类
https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805262953594880
PAT乙级1105 链表合并
https://pintia.cn/problem-sets/994805260223102976/exam/problems/1478634321389170688
PAT乙级1110 区块反转
https://pintia.cn/problem-sets/994805260223102976/exam/problems/1478634682663895040
总体分析：
1、几道题思路基本一致，都是用较大的数组模拟链表行为。
list数组下标作为节点地址，数组元素记录数据和下一节点地址。
struct Node
{
int addr;
int data;
int next;
}list[100001];
2、可以转到提取有效节点到新数组处理链表（1025、1075），也可以在大数组中直接处理（1105、1110）。
//按顺序提取链表到新数组
while(ptr != -1)
{
list1[length] = list[ptr];
list1[length].id = length;
length++;
ptr = list[ptr].next;
}
//链表的反转--直接在大数组处理
ptr2 = -1; int ptr2_next = head2;
while(ptr2_next != -1)
{
int temp = list[ptr2_next].next;
list[ptr2_next].next = ptr2;
ptr2 = ptr2_next;
ptr2_next = temp;
}
代码及分析：
PAT乙级1025 反转链表：
完成部分节点的反转，直接对部分节点进行排序比较清晰，因此在获取节点正确顺序后可以加入节点排序数据id。
根据k使用sort函数反转部分链表，反转后首尾节点的地址需要更新。
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct Node
{
int addr;
int data;
int next;
int id = 0;
}list[100001];
bool cmp(Node n1, Node n2)
{
return n1.id > n2.id;
}
int main()
{
int head, n, k;
cin >> head >> n >> k;
for(int i = 0; i < n; i++) //数据输入
{
int addr;
cin >> addr;
list[addr].addr = addr;
cin >> list[addr].data >> list[addr].next;
}
Node list1[n];
int ptr = head, length = 0;
while(ptr != -1) //将链表转移至小数组（只有有效节点被记录）
{
list1[length] = list[ptr];
list1[length].id = length; //为方便反转，添加一个id数据
length++;
ptr = list[ptr].next;
}
for(int i = 0;i < length; i += k) //根据id降序排列，即完成链表部分反转
{
if(i + k <= length)
{
sort(list1 + i, list1 + i + k, cmp);
}
}
for(int i = 0; i < length; i++) //输出反转后新的下一节点地址
{
printf("%05d %d ", list1[i].addr, list1[i].data);
if(i == length - 1) printf("-1\n");
else printf("%05d\n", list1[i+1].addr);
}
return 0;
}
PAT乙级1075 链表元素分类：
最开始的思路是将有效节点集中到一个数组后，根据特定规则排序；
cmp中：一个节点的数据>=0、一个<0的时候，则升序排；如果一个在[0，k]内，一个不在，则升序排；其他情况全不排。
bool cmp(Node n1, Node n2)
{
if((n1.data < 0 && n2.data >= 0) || (n1.data >= 0 && n2.data < 0))
return n1.data < n2.data;
else if((n1.data >= 0 && n1.data <= k && n2.data > k) ||
(n1.data > k && n2.data >= 0 && n2.data <= k))
return n1.data < n2.data;
else return false;
}
但是测试点5一直答案错误，未发现原因，后更改为将不同类型的节点一次存入三个数组，再按顺序输出即可。
#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
struct Node
{
int addr;
int data;
int next;
}list[100001];
int head, n, k;
int main()
{
cin >> head >> n >> k;
for(int i = 0; i < n; i++)
{
int addr;
cin >> addr;
list[addr].addr = addr;
cin >> list[addr].data >> list[addr].next;
}
int ptr = head;
Node list1[n], list2[n], list3[n];
int length1 = 0, length2 = 0, length3 = 0;
while(ptr != -1) //对不同的节点分类，存储到不同的数组去
{
if(list[ptr].data < 0)
{
list1[length1] = list[ptr];
length1++;
}
else if(list[ptr].data >= 0 && list[ptr].data <= k)
{
list2[length2] = list[ptr];
length2++;
}
else
{
list3[length3] = list[ptr];
length3++;
}
ptr = list[ptr].next;
}
//顺序输出三个数组
for(int i = 0; i < length1; i++)
{
printf("%05d %d ", list1[i].addr, list1[i].data);
if(i != length1 - 1) printf("%05d\n", list1[i + 1].addr);
else if(length2 == 0 && length3 == 0) printf("-1\n");
}
for(int i = 0; i < length2; i++)
{
if(i == 0 && length1 != 0) printf("%05d\n", list2[0].addr);
printf("%05d %d ", list2[i].addr, list2[i].data);
if(i != length2 - 1) printf("%05d\n", list2[i + 1].addr);
else if(length3 == 0) printf("-1\n");
}
for(int i = 0; i < length3; i++)
{
if(i == 0 && (length1 != 0 || length2 != 0)) printf("%05d\n", list3[0].addr);
printf("%05d %d ", list3[i].addr, list3[i].data);
if(i != length3 - 1) printf("%05d\n", list3[i + 1].addr);
else printf("-1\n");
}
return 0;
}
PAT乙级1105 链表合并：
思路：比较两个链表长度，反转短链表，长链表每两个节点间加入一个短链表节点。
直接在大数组中操作，行为和实际链表类似，新节点连接到长链表上一节点next，断掉新节点next指针，指向长链表下一节点。
#include<iostream>
#include<stdio.h>
using namespace std;
struct Node
{
int addr;
int data;
int next;
}list[100001];
int main()
{
int head1, head2, n;
cin >> head1 >> head2 >> n;
for(int i = 0; i < n; i++)
{
int addr;
cin >> addr;
list[addr].addr = addr;
cin >> list[addr].data >> list[addr].next;
}
int length1 = 0, length2 = 0;
int ptr1 = head1, ptr2 = head2;
while(ptr1 != -1 || ptr2 != -1) //记录比较两个链表长度
{
if(ptr1 != -1)
{
length1++;
ptr1 = list[ptr1].next;
}
if(ptr2 != -1)
{
length2++;
ptr2 = list[ptr2].next;
}
}
if(length1 < length2) //保证1长2短
{
int temp = head1; head1 = head2; head2 = temp;
temp = length1; length1 = length2; length2 = temp;
}
if(length2 > 1) //短链表反转
{
ptr2 = -1; int ptr2_next = head2;
for(int i = 0; i < length2; i++)
{
int temp = list[ptr2_next].next;
list[ptr2_next].next = ptr2;
ptr2 = ptr2_next;
ptr2_next = temp;
}
head2 = ptr2;
}
int cnt = 0; ptr1 = head1; ptr2 = head2;
while(ptr1 != -1) //长链表每两节点中间接入一个短链表节点，直接在大数组中操作
{
if(cnt == 1)
{
if(ptr2 != -1)
{
int temp = list[ptr1].next;
list[ptr1].next = list[ptr2].addr;
int temp2 = list[ptr2].next;
list[ptr2].next = temp;
ptr2 = temp2;
ptr1 = temp;
}
cnt = 0;
}
else
{
cnt++;
ptr1 = list[ptr1].next;
}
}
ptr1 = head1;
while(ptr1 != -1)
{
printf("%05d %d ", list[ptr1].addr, list[ptr1].data);
if(list[ptr1].next == -1) printf("-1\n");
else printf("%05d\n", list[ptr1].next);
ptr1 = list[ptr1].next;
}
return 0;
}
PAT乙级1110 区块反转：
每k个节点，断掉尾节点，并移位保存首节点和上一首节点地址，尾节点指向上一首节点。最后k（或者不到k）个节点的首节点，即为新链表的head。
#include<iostream>
#include<string>
using namespace std;
struct Node
{
int address;
int data;
int next_address;
}list[100001];
int main()
{
int head_address, n, k;
cin >> head_address >> n >> k;
for(int i = 0; i < n; i++)
{
int idx;
cin >> idx;
list[idx].address = idx;
cin >> list[idx].data >> list[idx].next_address;
}
int ptr_address = head_address;
int lastfirst = -1, first = -1;
int cnt = 0;
while(ptr_address != -1) //每k个节点，断掉尾节点next，指向上一部分k个节点的首节点
{
if(cnt == 0)
{
lastfirst = first;
first = ptr_address;
}
int temp_nextaddr;
if(cnt == k - 1 || list[ptr_address].next_address == -1)
{
temp_nextaddr = list[ptr_address].next_address;
list[ptr_address].next_address = lastfirst;
ptr_address = temp_nextaddr;
cnt = 0;
if(ptr_address == -1)
head_address = first;
}
else
{
cnt++;
ptr_address = list[ptr_address].next_address;
}
}
ptr_address = head_address;
while(ptr_address != -1)
{
printf("%05d %d ", list[ptr_address].address, list[ptr_address].data);
if(list[ptr_address].next_address != -1) printf("%05d\n", list[ptr_address].next_address);
else printf("-1\n");
ptr_address = list[ptr_address].next_address;
}
return 0;
}
#刷题记录#PAT乙级 文章被收录于专栏
PAT乙级（Basic）刷题记录
