CareerCup_2.1&2.2@1point3acres

2_1.cpp

/**********************************************************************

1.Write code to remove duplicates from an unsorted linked list 
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

2.Implement an algorithm to find the nth to last element of 
a singly linked list. (method: find_n())

***********************************************************************/

/**********************************************************************

			A simple list class.

***********************************************************************/


#include <iostream>
using namespace std;

class List
{
public:
	void unique();
	void insert(int k);
	void display();
	void find_n(int n);
	List():head(NULL), tail(NULL){}
	~List();
private:
	List(const List &);
	List& operator=(const List&);
	struct node
	{
		int key;
		node *next;
		node():key(0), next(NULL){}
	};
	node *head;
	node *tail;
	
};

List::~List()
{
	node *temp;
	if(head)
	{
		while(head != tail)
		{
			temp = head;
			head = head->next;
			delete temp;
		}
		delete tail;
	}
}

void List::insert(int k)
{
	node *temp = new node;
	temp->key = k;
	
	if(head == NULL)
	{
		head = temp;
		tail = temp;
	}
	else
	{
		tail->next = temp;
		tail = temp;
	}
}

void List::unique()
{
	node *cur = head;
	node *temp;
	node *pre = NULL;
	while(cur)
	{
		for(temp = head; temp != cur; temp = temp->next)
		{
			if(temp->key == cur->key)
			{
				break;
			}
		}
		if(temp != cur)
		{
			pre->next = cur->next;
			delete cur;
			cur = pre->next;
		}
		else
		{
			pre = cur;
			cur = cur->next;
		}
	}
	tail = pre;
}

void List::display()
{
	node *p = head;
	if(p == NULL)
		cout << "No element.";
	while(p)
	{
		cout << p->key << "\t";
		p = p->next;
	}
	cout << endl;
}

void List::find_n(int n)
{
	if(n <= 0)
	{
		cout << "parameter invalid." << endl;
		return;
	}
	if(head == NULL)
	{
		cout << "No elements in the list." << endl;
		return;
	}
	node *p = head;
	node *ans = NULL;
	int c = 0;
	while(p)
	{
		c++;
		if(c == n)
		{
			ans = p;
			break;
		}
		p = p->next;
	}
	if(ans == NULL)
		cout << "No " << n << " elements in the list." << endl;
	else
	{
		while(ans)
		{
			cout << ans->key << "\t";
			ans = ans->next;
		}
		cout << endl;
	}
}

int main()
{
	List lst;
	for(int i = 1; i <= 10; i++)
	{
		lst.insert(i);
		lst.insert(i);
	}
	lst.unique();
	lst.display();
	lst.find_n(5);
	return 0;
}