C++ 實現(xiàn)L2-002 鏈表去重

更新時間：2021年07月06日 15:55:19 作者：一只特立獨行的貓

這篇文章主要介紹了C++ 實現(xiàn)L2-002 鏈表去重,本文通過簡要的案例,解題思路講解了該項技術的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下

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

輸入格式：

輸入在第一行給出 L 的第一個結點的地址和一個正整數(shù) N（≤105，為結點總數(shù)）。一個結點的地址是非負的 5 位整數(shù)，空地址 NULL 用 −1 來表示。

隨后 N 行，每行按以下格式描述一個結點：

地址鍵值下一個結點

其中地址是該結點的地址，鍵值是絕對值不超過104的整數(shù)，下一個結點是下個結點的地址。

輸出格式：

首先輸出去重后的鏈表，然后輸出被刪除的鏈表。每個結點占一行，按輸入的格式輸出。

輸入樣例：

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

思路：
很多辦法都可以實現(xiàn)，我選擇數(shù)組模擬動態(tài)內(nèi)存，先建立一個鏈表再遍歷，時間復雜度是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];//開辟一片模擬內(nèi)存
int flag[10001];//標記結點

int main() {
	int num, startM;//p標記當前節(jié)點
	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;
	}//鏈表構建完成

	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++ 實現(xiàn)L2-002 鏈表去重的文章就介紹到這了,更多相關C++ 鏈表去重內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: