CC150 2.1

2_1.cpp

/* CC150 2.1
 * Write code to remove duplicates from an unsorted linked list.
 * How would you solve this problem if a temporary buffer is not allowed?
 */

#include <iostream>
#include <list>
#include <vector>

using namespace std;

void removeDup(list<char> &clst)
{
	vector<bool> flag(256, false);
	auto begin = clst.begin(), end = clst.end();
	while (begin != end) {
		if (!flag[*begin])
			flag[*begin++] = true; // mark as appeard when first time see a character
		else
			begin = clst.erase(begin); // remove duplicates
	}
	return;
}

void removeDupBrute(list<char> &clst)
{
	auto begin = clst.begin(), end = clst.end();
	while (begin != end) {
		auto del = begin; // set runner one element ahead of begin
		++del;
		while (del != end) {
			if (*del != *begin) // remove duplicates
				++del;
			else
				del = clst.erase(del);
		}
		++begin; // advance to the next character
	}
	return;
}

int main()
{
	list<char> clst;
	char c;
	while (cin >> c)
		clst.push_back(c);
	removeDup(clst);
	for (auto c : clst)
		cout << c << " ";
	cout << endl;
	return 0;
}