Untitled

#include <iostream>
using namespace std;

class Node
{
public:
	int data;
	Node *next,*prev;
};
//noi
void conect(Node *a,Node *b){
	a->next=b;
	b->prev=a;
}
class LL

{
public:
	Node *head,*tail;
	LL(){
		head=new Node();
		tail=new Node();
		conect(head,tail);
	}
	//them vao dau
	void addFirst(int val){
		Node *newNode=new Node();
		newNode->data=val;
		Node *n=head->next;
		conect(newNode,n);
		conect(head,newNode);
	}
	//them vao cuoi
	void addLast(int val){
		Node *newNode= new Node();
		newNode->data=val;
		Node *p=tail->prev;
		conect(p,newNode);
		conect(newNode,tail);
	}
	//them vao sau cur
	void addAfter(Node *cur,int val){
		Node *newNode= new Node();
		newNode->data=val;
		Node *n=cur->next;
		conect(newNode,n);
		conect(cur,newNode);
	}
	//check rong
	bool isEmpty(){
		return head->next==tail;
	}
	//xoa dau
	Node *delFirst(){
		if(isEmpty()) return nullptr;
		Node *h=head->next;
		conect(head,h->next);
		return h;
	}
	//xoa cuoi
	Node *delLast(){
		if(isEmpty()) return nullptr;
		Node *t=tail->prev;
		conect(t->prev,tail);
		return t;
	}
	//xoa n
	Node *delMid(Node *n){
		if(isEmpty()) return nullptr;
		conect(n->prev,n-> next);
	}
    //chuyen list 2 vao sau list 
	void merge(LL *link2){
		if(link2->isEmpty()) return;
		Node *n2=link2->head->next;
		Node *p2=link2->tail->prev;
		Node *p1=tail->prev;
		conect(p1,n2);
		conect(p2,tail);
		conect(link2->head,link2->tail);
	}
	void print(){
		Node *cur=head->next;
		while(cur!=tail){
			cout<<cur->data<<" ";
			cur=cur->next;
		}
	}
};


int main(){
	//freopen("input.txt","r",stdin);
	LL l1;
	l1.addLast(33);
	l1.addLast(55);
	l1.addLast(88);

	LL l2;
	l2.addLast(44);
	l2.addLast(77);
	l2.addLast(99);
	l1.merge(&l2);
	l1.print();
	return 0;
}