L2-002 链表去重
题目 L2-002 链表去重
思路分析
尽力了孩子们 康复训练下马威 绞尽脑汁回忆起模拟链表怎么写
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
unordered_map<int,PII> node;
unordered_map<int,PII> del_node;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int head,n;cin>>head>>n;
while(n--){
int idx,var,next;cin>>idx>>var>>next;
node[idx]={var,next};
}
set<int> have_exist;
del_node[-1]={0,-1};
int curDelNail=-1;
for(int i=head;i!=-1;i=node[i].second){
// cout<<node[i].first<<endl;
// 因为需要删除节点 更改next域 如果走到该点发现要删除 需要索引回上一个点
// 三种办法
// 一：更改结构 记录上一个节点的地址
// 二：用一个前驱先一步去探
// 三：借尸还魂 把下一个的值全拷过来 把下一个删掉 这样链不会出问题 但这里不适用 本质地址没变 结果要输出该点的地址
// 改结构太麻烦了 还是用第二种吧 用一个先锋去探下一个位置要不要删
have_exist.insert(abs(node[i].first)); //因为是看下一个点删不删 所以先要把当前点放进去
int pre = node[i].second;
if(have_exist.find(abs(node[pre].first))!=have_exist.end()){
// node[i].second=node[pre].second;
// 删除的节点又要形成一个新链表 怎么处理
// 又要是尾插法 留个尾巴在这 等着赋值？
del_node[curDelNail].second = node[i].second;
del_node[node[i].second]={node[pre].first,-1};
curDelNail=node[i].second;
node[i].second=node[pre].second;
}
}
for(int i=head;i!=-1;i=node[i].second){
printf("%05d %d %d\n",i,node[i].first,node[i].second);
}
for(int i=del_node[-1].second;i!=-1;i=del_node[i].second){
printf("%05d %d %d\n",i,del_node[i].first,del_node[i].second);
}
return 0;
}
代码实现
原链表的node已经存储了所有节点，无需新开del_node单独存储删除的节点，直接复用node结构，用del_head和del_tail维护删除链表的头和尾。
在处理当前节点时检查下一个节点是否需要删除，但此时当前节点的next可能已被修改，导致循环跳过节点。 （1→2→3→4 2被删除 1→3→4 走到3 看下一步4要不要删 而3被忽略了检查 所以还是得记录前驱节点 检查当前节点）
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
unordered_map<int,PII> node;
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int head,n;cin>>head>>n;
while(n--){
int idx,var,next;cin>>idx>>var>>next;
node[idx]={var,next};
}
set<int> seen_abs;
int del_head = -1, del_tail = -1;
int prev = -1; // 前驱节点地址
int curr = head; // 当前节点地址
while(curr!=-1){
int curr_abs=abs(node[curr].first);
if (seen_abs.count(curr_abs)) {
// 需要删除当前节点
if (prev != -1) {
node[prev].second = node[curr].second; // 前驱跳过当前节点
} else {
head = node[curr].second; // 更新头节点
}
// 将当前节点加入删除链表
if (del_head == -1) {
del_head = del_tail = curr;
} else {
node[del_tail].second = curr;
del_tail = curr;
}
node[curr].second = -1; // 断开原有连接
curr = node[prev].second; // 移动到下一个节点
} else {
seen_abs.insert(curr_abs);
prev = curr;
curr = node[curr].second;
}
}
for(int i=head;i!=-1;i=node[i].second){
printf("%05d %d ", i, node[i].first);
if (node[i].second == -1) printf("-1\n");
else printf("%05d\n", node[i].second);
}
for(int i=del_head;i!=-1;i=node[i].second){
printf("%05d %d ", i, node[i].first);
if (node[i].second == -1) printf("-1\n");
else printf("%05d\n", node[i].second);
}
return 0;
}
同类题型
视频讲解
⬅️ L2-001 紧急救援 🏠 00-天梯赛 ➡️ L2-003 月饼
💬 评论