#include <iostream>
#include <time.h>
#define SIZE 20
using namespace std;

struct node {
	int data;
	node *pNext;
};

node* getNode(int x) {
	node *p = new node;
	if (p == NULL)
		return NULL;
	p->data = x;
	p->pNext = NULL;
	return p;
}

//Problem 1b / lab3
void InsertTail(node*& head, int newdata) {
	node *p = getNode(newdata);
	if (head == NULL)
	{
		head = p;
	}
	node *k = head;
	for (k; k->pNext != NULL; k = k->pNext)
	{
		if (k->pNext == NULL) break;
	}
	k->pNext = p;
	p->pNext = NULL;
}

//Problem 1a / lab3
node* CreateListRanDom(int n) {
	int x;
	node *head = NULL;
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		x = rand() % 100; //sinh ngẫu nhiên giá trị x từ 0 -> 99
		InsertTail(head, x);
	}
	return head;
}

//Problem 1c / lab3
void InsertHead(node*& head, int newdata) {
	node *p = getNode(newdata);
	p->pNext = head;
	head = p;
}

//Problem 1d / lab3
void DeleteData(node *&pHead, int delData) {
	node *k = pHead;
	node *r = new node;
	node *p = new node;

	//Cái vòng lặp for này là để tìm ra node cuối cùng để thao tác những lệnh đằng sau
	node *tail = pHead;
	for (tail; tail->pNext != NULL; tail = tail->pNext)
	{
		if (tail->pNext == NULL)
			break;
	}

	//trường hợp node cần xóa nằm ở đầu danh sách
	if ((pHead->data) == delData)
	{
		p = pHead;
		pHead = pHead->pNext;
		delete p;
	}

	//trường hợp node cần xóa nằm ở cuối danh sách
	else if ((tail->data == delData))
	{
		for (k; k->pNext != tail; k = k->pNext);
		delete tail;
		tail = k;
		k->pNext = NULL;
	}

	////trường hợp node cần xóa nằm ở giữa danh sách
	else
	{
		for (k; k->pNext; k = k->pNext)
		{
			if ((k->pNext)->data == delData)
			{
				p = k->pNext;
				r = (k->pNext)->pNext;
				break;
			}
		}
		k->pNext = r;
		delete p;
	}
}

void PrintLinkedList(node* head) {
	for (node *p = head; p; p = p->pNext)
	{
		cout << p->data << "  ";
	}
}

int main() {
	int n;
	cin >> n;
	node *LinkedList = CreateListRanDom(n);
	InsertHead(LinkedList, 28);
	InsertTail(LinkedList, 9);
	PrintLinkedList(LinkedList);
	int delData;
	cout << endl;
	cout << "Enter delData: ";
	cin >> delData;
	DeleteData(LinkedList, delData);
	PrintLinkedList(LinkedList);
	system("pause");
}