怎么用C++實(shí)現(xiàn)L2-002鏈表去重

本篇內(nèi)容介紹了“怎么用C++實(shí)現(xiàn)L2-002鏈表去重”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

給定一個(gè)帶整數(shù)鍵值的鏈表 L，你需要把其中絕對(duì)值重復(fù)的鍵值結(jié)點(diǎn)刪掉。即對(duì)每個(gè)鍵值 K，只有第一個(gè)絕對(duì)值等于 K 的結(jié)點(diǎn)被保留。同時(shí)，所有被刪除的結(jié)點(diǎn)須被保存在另一個(gè)鏈表上。例如給定 L 為 21→-15→-15→-7→15，你需要輸出去重后的鏈表 21→-15→-7，還有被刪除的鏈表 -15→15。

輸入格式：

輸入在第一行給出 L 的第一個(gè)結(jié)點(diǎn)的地址和一個(gè)正整數(shù) N（≤105，為結(jié)點(diǎn)總數(shù)）。一個(gè)結(jié)點(diǎn)的地址是非負(fù)的 5 位整數(shù)，空地址 NULL 用 ?1 來(lái)表示。

隨后 N 行，每行按以下格式描述一個(gè)結(jié)點(diǎn)：

地址 鍵值 下一個(gè)結(jié)點(diǎn)

其中地址是該結(jié)點(diǎn)的地址，鍵值是絕對(duì)值不超過(guò)104的整數(shù)，下一個(gè)結(jié)點(diǎn)是下個(gè)結(jié)點(diǎn)的地址。

輸出格式：

首先輸出去重后的鏈表，然后輸出被刪除的鏈表。每個(gè)結(jié)點(diǎn)占一行，按輸入的格式輸出。

輸入樣例：

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

思路：
很多辦法都可以實(shí)現(xiàn)，我選擇數(shù)組模擬動(dòng)態(tài)內(nèi)存，先建立一個(gè)鏈表再遍歷，時(shí)間復(fù)雜度是O(n)，格式控制還是printf好用。

#include<iostream>
#include<cstdio>
#include<cmath>
#define NULL -1

using namespace std;

typedef struct node {
	int val;
	unsigned int next;
}node;

node store[100001];//開(kāi)辟一片模擬內(nèi)存
int flag[10001];//標(biāo)記結(jié)點(diǎn)

int main() {
	int num, startM;//p標(biāo)記當(dāng)前節(jié)點(diǎn)
	cin >> startM >> num;

	for (int i = 0; i < num; i++) {
		int now, val, next;
		cin >> now >> val >> next;
		store[now].val = val;
		store[now].next = next;
	}//鏈表構(gòu)建完成

	int p1=startM,startS=NULL;
	int p2 = 100000,pre;
	bool k = true;
	while (p1 != NULL) {
		if (flag[abs(store[p1].val)] != 0) {
			store[pre].next = store[p1].next;
			store[p2].next = p1;
			store[p1].next = NULL;
			p2 = p1;
			if (k) {
				k = false;
				startS = p2;
			}
			p1 = store[pre].next;
		}
		else {
			flag[abs(store[p1].val)] = 1;
			pre = p1;
			p1 = store[p1].next;
		}
	}//鏈表查重完成

	p1 = startM;
	while (p1 != NULL) {
		if(store[p1].next!=NULL)
			printf("%05d %d %05d\n",p1, store[p1].val, store[p1].next);
		else
			printf("%05d %d %d\n", p1, store[p1].val, store[p1].next);
		p1 = store[p1].next;
	}
	p1 = startS;
	while (p1 != NULL) {
		if (store[p1].next != NULL)
			printf("%05d %d %05d\n", p1, store[p1].val, store[p1].next);
		else
			printf("%05d %d %d\n", p1, store[p1].val, store[p1].next);
		p1 = store[p1].next;
	}
	return 0;
}

“怎么用C++實(shí)現(xiàn)L2-002鏈表去重”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！