有无大神看看,每次写链表的时候dev都能运行,但提交到洛谷就全RE了,自己找不到问题
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct Node { // 创建节点结构
int num; // 节点存储的数值
Node* next; // 指向下一个节点的指针
Node* last; // 指向前一个节点的指针
};
Node* head; // 头节点指针
Node* nil; // 尾节点指针,用于双向循环链表的尾部
// 初始化函数,建立两个节点:头节点和尾节点
int init() {
head = new Node; // 创建头节点
nil = new Node; // 创建尾节点
head->num = 1; // 头节点存储数值 1
nil->num = 0; // 尾节点存储数值 0
head->next = NULL;
head->last = NULL;
nil->next = NULL;
nil->last = NULL;
// 构建双向循环链表
head->next = nil; // 头节点的 next 指向尾节点
head->last = nil; // 头节点的 last 指向尾节点
nil->next = head; // 尾节点的 next 指向头节点
nil->last = head; // 尾节点的 last 指向头节点
}
signed main() {
init(); // 调用初始化函数
int n; // 输入节点数量
cin >> n;
// 循环插入节点,构建链表
for (int i = 2; i <= n; i++) { // 从编号 2 开始插入节点
int k, p; // 输入目标节点编号 k 和插入位置 p
cin >> k >> p;
Node* pi = head; // 从头节点开始遍历
Node* po = new Node; // 创建新节点
po->num = i; // 新节点编号为 i
// 找到目标节点 k
while (pi->num != k) {
pi = pi->next;
}
// 根据 p 的值决定插入位置
if (p == 1) { // 插入到目标节点 k 的后面
po->next = pi->next; // 新节点的 next 指向目标节点的下一个节点
po->last = pi; // 新节点的 last 指向目标节点
pi->next->last = po; // 目标节点的下一个节点的 last 指向新节点
pi->next = po; // 目标节点的 next 指向新节点
} else if (p == 0) { // 插入到目标节点 k 的前面
po->next = pi; // 新节点的 next 指向目标节点
po->last = pi->last; // 新节点的 last 指向目标节点的前一个节点
pi->last->next = po; // 目标节点的前一个节点的 next 指向新节点
pi->last = po; // 目标节点的 last 指向新节点
}
}
// 删除操作
int m; // 输入需要删除的节点数量
cin >> m;
for (int i = 0; i < m; i++) { // 循环删除节点
int a; // 输入需要删除的节点编号
cin >> a;
Node* pe = nil->next; // 从头节点开始遍历
while (pe != nil) { // 遍历链表直到尾节点
if (pe->num == a) { // 找到需要删除的节点
pe->next->last = pe->last; // 删除节点的下一个节点的 last 指向删除节点的前一个节点
pe->last->next = pe->next; // 删除节点的前一个节点的 next 指向删除节点的下一个节点
delete pe; // 删除节点
break; // 跳出循环
}
pe = pe->next; // 移动到下一个节点
}
}
// 遍历链表并输出结果
Node* pr = nil->next; // 从头节点开始遍历
do {
if (pr->num) // 如果节点编号不为 0(尾节点的编号为 0)
cout << pr->num << ' '; // 输出节点编号
pr = pr->next; // 移动到下一个节点
} while (pr != nil); // 直到遍历到尾节点
cout << '\n';
return 0;
}