題目

思路：

• 先把題目中的鏈表讀進(jìn)內(nèi)存
• 創(chuàng)建兩個(gè)新鏈表listA, listB
• 遍歷原鏈表，把重復(fù)的放進(jìn)listB，不重復(fù)的放進(jìn)listA。放的時(shí)候，注意處理一下后繼next中存的值。
• 分別打印兩個(gè)分離的鏈表listA，listB，注意補(bǔ)全5位address的前導(dǎo)0

---

題解 C++

每次提交結(jié)果不完全一樣，有時(shí)候后兩個(gè)測(cè)試點(diǎn)運(yùn)行超時(shí)，有時(shí)候全部AC。
實(shí)際比賽的時(shí)候，也要多試幾次（上次就是，提交多次，結(jié)果有微小差別）。

#include<iostream> #include<math.h> #include<iomanip> #define SIZE 10000 using namespace std; class Node { public:int addr = -1;int key; //0-10000int next = -1;bool isSame = false; //標(biāo)記key是否重復(fù) }; int main() {Node list[SIZE]; //0-100000 數(shù)組存儲(chǔ)鏈表 下標(biāo)代表地址int firstNotSame, total;cin >> firstNotSame >> total;//輸入鏈表int addr;for (int i = 0; i < total; i++) {cin >> addr;list[addr].addr = addr;//便于輸出cin >> list[addr].key >> list[addr].next;}//遍歷鏈表：拆分Node listA[SIZE];int sizeA = 0;Node listB[SIZE];int sizeB = 0;bool hasKey[10000] = { false };//標(biāo)記該key是否存在Node cur = list[firstNotSame];while (true) {if (!hasKey[abs(cur.key)]) {//key不存在hasKey[abs(cur.key)] = true;//存入Aif (sizeA != 0) {listA[sizeA - 1].next = cur.addr;}listA[sizeA] = cur;listA[sizeA].next = -1;sizeA++;}else {//存入Bif (sizeB != 0) {listB[sizeB - 1].next = cur.addr;}listB[sizeB] = cur;listB[sizeB].next = -1;sizeB++;}if (cur.next == -1) {break;}else {cur = list[cur.next];}}//輸出兩個(gè)(偽)鏈表for (int i = 0; i < sizeA; i++) {cout << setw(5) << setfill('0') << listA[i].addr << " ";//處理前導(dǎo)0cout << listA[i].key << " ";if (listA[i].next == -1)cout << "-1\n"; //處理前導(dǎo)0else cout << setw(5) << setfill('0') << listA[i].next << endl;}for (int i = 0; i < sizeB; i++) {cout << setw(5) << setfill('0') << listB[i].addr << " ";//處理前導(dǎo)0cout << listB[i].key << " ";if (listB[i].next == -1)cout << "-1\n"; //處理前導(dǎo)0else cout << setw(5) << setfill('0') << listB[i].next << endl;}system("pause"); }

總結(jié)

以上是生活随笔為你收集整理的【PAT甲级 链表去重】1097 Deduplication on a Linked List (25 分) C++ 全部AC的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。