#include<iostream>
using namespace std;


//khai bao cau truc 1 node//
struct node {
	int data;
	struct node *pNext;//con tro lien ket cac node voi nhau//
};

//khai bao cau truc danh sach lien ket don//
struct list {
	node *pHead;//con tro de quan li danh sach lien ket don//
	node *pTail;
};

//khoi tao danh sach lien ket don//
void Init(list &l) {
	l.pHead = l.pTail = NULL;

}


//tao mot node moi//
node* Getnode(int DATA){
	node* p = new node;//cap phat vung nho cho NODE p//
	if (p == NULL) {
		return NULL;
	}
	p->data = DATA;// dua data vao trong node//
	p->pNext = NULL;//khai bao node nay chua lien ket voi node nao ca. nen con tro nay la NULL//
	return p;//tra ve node vua khoi tao//
}


//them node p vao dau, p vao cuoi danh sach//
void addHead(list &l,node *p) {
	if (l.pHead == NULL) {
		l.pHead = l.pTail = p;
	}
	else {
		p->pNext = l.pHead; //dung con tro cua node p tro toi dau danh sach pHead//
		l.pHead = p;       //cap nhat lai dau danh sach//
	}
}

void addTail(list& l, node* p) {
	if (l.pHead == NULL) {
		l.pHead = l.pTail = p;
	}

	else {
		l.pTail->pNext = p;//pTail tro next toi p
		l.pTail = p;//cap nhat pTail chinh la p//

	}
}




void input(list &l) {
	int n;
	cout << "\nnhap vao so luong phan tu trong danh sach";
	cin >> n;
	for (int i = 1; i <=n; i++) {
		int data;
		cout << "\nnhap vao data:";
		cin >> data;
		//dong goi data vao node//
		node* p = Getnode(data);//khoi tao 1 node//
		addHead(l, p);//them node p vao dau danh sach//
	}
}


void output(list l) {
	for (node* p = l.pHead; p != NULL; p = p->pNext) {
		cout << p->data<<"     ";
	}

}

void giaiphong(list& l) {
	node* p;
	while (l.pHead != NULL) {
		p = l.pHead;
		l.pHead = l.pHead->pNext;
		delete p;
	}
}

int tinhtong(list l) {
	int tong = 0;
	for (node* p = l.pHead; p != NULL; p = p->pNext) {
		tong += p->data;
	}
	return tong;
}

void lietkesochan(list l) {
	for (node* p = l.pHead; p != NULL; p=p->pNext) {
		if (p->data % 2 == 0) {
			cout << p->data<<"  ";
		}
	}
}

void hoanvi(int & x, int &y) {
	int temp = x;
	x = y;
	y = temp;
}

bool lonhon(int a, int b) {
	return a > b;
}
bool nhohon(int a, int b) {
	return a < b;
}


void sapxepdanhsach(list& l, bool(*sosanh)(int,int)) {
	for (node* p = l.pHead; p != NULL; p = p->pNext) {
		for (node* q = p->pNext; q != NULL; q = q->pNext) {
			if ((sosanh)(p->data, q->data) == true){
			      hoanvi(p->data, q->data);
			}
		}
	}
}

int timMinMax(list l, bool(*sosanh)(int, int)) {
	int m = l.pHead->data;
	for (node* p = l.pHead; p != NULL; p = p->pNext) {
		for (node* q = p->pNext; q != NULL; q = q->pNext) {
			if ((sosanh)(p->data, q->data) != true) {
				m= p->data;
			}
		}
	}
	return m;

}
//them node x vao sau node q trong danh sach//
void themvaosau(list& l, node* x, node* q) {
	for (node* p = l.pHead; p != NULL; p = p->pNext) {
		if (p->data == q->data) {
			node* g = p->pNext;//node g la node nam sau node x//
			x->pNext = g;//cho node x lien ket voi node g//
			p->pNext = x;//cho node p lien ket voi node x//
			return;
		}
	}
}


int main() {
	list l;//khai bao danh sach
	Init(l);
	input(l);
	output(l);
	int tong = tinhtong(l);
	cout << "\ntong cac phan tu cua danh sach S= " << tong;
	cout << "\ncac so chan trong danh sach: ";
	lietkesochan(l);
	cout << "\nsap xep tang: ";
	sapxepdanhsach(l, lonhon);
	output(l);
	cout<<"\n--------------------\n";
	cout << "\nsap xep giam: ";
	sapxepdanhsach(l, nhohon);
	output(l);
	int max=timMinMax(l, lonhon);
	cout << "\n--------------------\n";
	cout << "\nphan tu lon nhat trong danh sach: "<<max;
	int min=timMinMax(l, nhohon);
	cout << "\nphan tu nho nhat trong danh sach: "<<min;
	cout << "\n--------------------\n";
	cout << "\nthem node vao danh sach lien ket";
	node* q;
	node* x;
	int s, t;
	cout << "\nnhap vao node can them vao sau:";
	cin >> s;
	q = Getnode(s);
	cout << "\nnhap vao node muon them: ";
	cin >> t;
	x = Getnode(t);
	themvaosau(l, x, q);
	output(l);
	giaiphong(l);
	return 0;
}