L2-002 鏈表去重 (25分)
給定一個帶整數鍵值的鏈表 L，你需要把其中絕對值重復的鍵值結點刪掉。即對每個鍵值 K，只有第一個絕對值等于 K 的結點被保留。同時，所有被洗掉的結點須被保存在另一個鏈表上。例如給定 L 為 21→-15→-15→-7→15，你需要輸出去重后的鏈表 21→-15→-7，還有被洗掉的鏈表 -15→15。
輸入格式：
輸入在第一行給出 L 的第一個結點的地址和一個正整數 N（≤105，為結點總數）。一個結點的地址是非負的 5 位整數，空地址 NULL 用 ?1 來表示。
隨后 N 行，每行按以下格式描述一個結點：
地址 鍵值 下一個結點
其中地址是該結點的地址，鍵值是絕對值不超過104的整數，下一個結點是下個結點的地址。
輸出格式：
首先輸出去重后的鏈表，然后輸出被洗掉的鏈表。每個結點占一行，按輸入的格式輸出。
輸入樣例：
00100 5
99999 -7 87654
23854 -15 00000
87654 15 -1
00000 -15 99999
00100 21 23854
輸出樣例：
00100 21 23854
23854 -15 99999
99999 -7 -1
00000 -15 87654
87654 15 -1
第二個測驗點一直過不去，想了好幾種邊界情況都輸出正確，請問大佬到底是哪里的問題？
#include <bits/stdc++.h>
#define MAXN 1005000
int pre[MAXN],val[MAXN],next[MAXN],m[MAXN];
int main(){
int head,n;
std::cin>>head>>n;
for(int i=0;i<n;i++){
int a,b,c;std::cin>>a>>b>>c;
next[a]=c;val[a]=b;
if(c>=0) pre[c]=a;
}
int another_head=-1,another_tail=-1;
for(int ptr=head;ptr!=-1;ptr=next[ptr]){
if(m[std::abs(val[ptr])]){
next[pre[ptr]]=next[ptr];
if(next[ptr]>=0) pre[next[ptr]]=pre[ptr];
if(another_head==-1){
another_head=ptr;
another_tail=ptr;
}else{
next[another_tail]=ptr;
pre[ptr]=another_tail;
another_tail=ptr;
}
}else m[std::abs(val[ptr])]=1;
}
if(another_tail>=0)
next[another_tail]=-1;
for(int ptr=head;ptr!=-1;ptr=next[ptr]){
printf("%05d %d ",ptr,val[ptr]);
next[ptr]==-1?printf("-1\n"):printf("%05d\n",next[ptr]);
}
for(int ptr=another_head;ptr!=-1;ptr=next[ptr]){
printf("%05d %d ",ptr,val[ptr]);
next[ptr]==-1?printf("-1\n"):printf("%05d\n",next[ptr]);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/131850.html
標籤：C++ 語言
上一篇：vc6.0
下一篇：這個運算式怎么弄？