Vũ Hoàng Diệu Linh

/*
   Cho danh sách L, hãy đảo ngược danh sách
*/

#include<bits/stdc++.h>

using namespace std;

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

int n;
node * L = NULL;
node * L2;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q;
       R = q;
   } else {
       R->next = q;
       R = q;
   }
}

void out(node *&L){
   node * p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

void reverseList(node * L1,node * &L2){
   node * p, * q, *pre;
   p = L1; L2 = NULL;
   while (p != NULL){
       q = new node;
       q->data = p->data;
       q->next = L2;
       L2 = q;
       p = p->next;
   }
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cin >> n;
   int x;
   for(int i = 1; i <= n; i++){
       cin >> x;
       IS(L, x);
   }
   out(L);
   cout << '\n';
   reverseList(L, L2);
   out(L2);
   return 0;
}

/*
   Cho hai danh sách L1, L2 là 2 dãy đơn điệu tăng.
   Tìm giao của 2 danh sách
*/  

#include<bits/stdc++.h>

using namespace std;

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

node * L1 = NULL;
node * L2 = NULL;
node * L3 = NULL;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q;
       R = q;
   } else{
       R->next = q;
       R = q;
   }
}

void insertL1L2(node * L1, node * L2, node *&L3){
   node *p, *q, *lastL3, *r;
   p = L1;
   q = L2;
   lastL3 = NULL;
   L3 = NULL;
   while(p != NULL && q != NULL){
       if(p->data < q->data) p = p->next;
           else if(p->data == q->data){
               IS(L3, p->data);
               p = p->next;
           }
               else q = q->next;
   }
}

void out(node *L){
   node *p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
   cout << '\n';
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int n, m;
   int x;
   cin >> n >> m;
   for(int i = 1; i <= n; i++){
       cin >> x;
       IS(L1, x);
   }
   for(int i = 1; i <= m; i++){
       cin >> x;
       IS(L2, x);
   }
   out(L1);
   out(L2);
   insertL1L2(L1, L2, L3);
   out(L3);
   return 0;
}

/*
   Cho dãy N số, X;
   Xóa các giá trị bằng x trong dãy.
*/

#include<bits/stdc++.h>

using namespace std;

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

node * L = NULL;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q;
       R = q;
   } else{
       R->next = q;
       R = q;
   }
}

node *find(node *L, int u){ // trả về node thứ u của danh sách
   node *p = L;
   while(p != NULL && p->data != u) p = p->next;
   return p;
}

void X_dele(node *&L, int x){ // xóa một node có giá trị bằng x
   node * p = find(L, x);
   node * pre;
   pre = L;
   while(pre->next != p) pre = pre->next;
   node * tmp = p -> next;
   pre->next = tmp;
   delete p;
}

void out(node *&L){
   node * p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int n;
   int x;
   cin >> n;
   for(int i = 1; i <= n; i++){
       cin >> x;
       IS(L, x);
   }
   out(L);
   cout << '\n';
   cin >> x;
   X_dele(L, x);
   out(L);
   return 0;
}

/*
   Cho dãy N số nguyên, k, x
   Chèn x vào sau node có giá trị k
*/

#include<bits/stdc++.h>

const int nmax = 100007;

using namespace std;

int n;
int a[nmax];

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

node * L = NULL;

void IS(node * &L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q;
       R = q;
   } else{
       R->next = q;
       R = q;
   }
}

void out(node *L){
   node *p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

node *find(node *L, int u){ // trả về node thứ u của danh sách
   node *p = L;
   while(p != NULL && p->data != u) p = p->next;
   return p;
}

void PB(node *&L, int x, int y){ // thuật: Tạo node mới q, gán gtri cho q, trỏ q vào node sau p, trỏ p vào q
   node *p = find(L, y);
   node * q;
   q = new node;
   q->data = x;
   q->next = p->next;
   p->next = q;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cin >> n;
   int x;
   for(int i = 1; i <= n; i++){
       cin >> x;
       IS(L, x);
   }
   out(L);
   cout << '\n';
   int k;
   cin >> x >> k;
   PB(L, x, k);
   out(L);
   return 0;
}

/*
   Cho danh sách L, in danh sách L ra
*/

#include<bits/stdc++.h>

using namespace std;

int n;

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

node *L = NULL;

void IS(node *&L, int u){
   node * q, * R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q;
       R = q;
   } else{
       R->next = q;
       R = q;
   }
}

void out(node *&L){
   node * p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cin >> n;
   int x;
   for(int i = 1; i <= n; i++){
       cin >> x;
       IS(L, x);
   }
   out(L);
   return 0;
}

// Đếm số lượng node của danh sách L

#include<bits/stdc++.h>

using namespace std;

int n;

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

node * L = NULL;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q; R = q;
   }else{
       R->next = q;
       R = q;
   }
}

int Count_Node(node *&L){
   int res = 0;
   node *p = L;
   while(p != NULL){
       res++;
       p = p->next;
   }
   return res;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int x;
   cin >> n;
   for(int i = 1; i <= n; i++){
       cin >> x;
       IS(L, x);
   }
   cout << Count_Node(L);
   return 0;
}

// Kiem tra x co xuat hien trong danh sach k
#include<bits/stdc++.h>

using namespace std;

int n;

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

node * L = NULL;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q; R = q;
   }else{
       R->next = q;
       R = q;
   }
}

bool X_check(node *&L, int x){
   node *p = L;
   while(p != NULL){
       if(p->data == x) return true;
       p = p->next;
   }
   return false;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int x;
   cin >> n;
   for(int i = 1; i <= n; i++){
       cin >> x;
       IS(L, x);
   }
   cout << X_check(L, x);
   return 0;
}

// Nếu x chưa có trong danh sách, chèn x vào cuối danh sách

#include<bits/stdc++.h>

using namespace std;

int n;

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

node * L = NULL;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q; R = q;
   }else{
       R->next = q;
       R = q;
   }
}

bool X_check(node *&L, int x){
   node *p = L;
   while(p != NULL){
       if(p->data == x) return true;
       p = p->next;
   }
   return false;
}

void out(node *&L){
   node *p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int x, y;
   cin >> n >> x;
   for(int i = 1; i <= n; i++){
       cin >> y;
       IS(L, y);
   }
   if(!X_check(L, x)) IS(L, x);
   out(L);
   return 0;
}

// chèn x vào đầu danh sách

#include<bits/stdc++.h>

using namespace std;

int n;

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

node * L = NULL;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q; R = q;
   }else{
       R->next = q;
       R = q;
   }
}

bool X_check(node *&L, int x){
   node *p = L;
   while(p != NULL){
       if(p->data == x) return true;
       p = p->next;
   }
   return false;
}

void out(node *&L){
   node *p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

void IS_Head(node *&L, int x){
   node * q;
   q = new node;
   q->data = x;
   q->next = L;
   L = q;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int x, y;
   cin >> n >> x;
   for(int i = 1; i <= n; i++){
       cin >> y;
       IS(L, y);
   }
   IS_Head(L, x);
   out(L);
   return 0;
}

// xóa node đầu tiên của danh sách

#include<bits/stdc++.h>

using namespace std;

int n;

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

node * L = NULL;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q; R = q;
   }else{
       R->next = q;
       R = q;
   }
}

void out(node *&L){
   node *p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

void Delete_Head(node *&L){
   if(L == NULL) return;
   node *p = L;
   L = L->next;
   delete p;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int x, y;
   cin >> n >> x;
   for(int i = 1; i <= n; i++){
       cin >> y;
       IS(L, y);
   }
   Delete_Head(L);
   out(L);
   return 0;
}

// xóa node cuối cùng của danh sách

#include<bits/stdc++.h>

using namespace std;

int n;

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

node * L = NULL;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q; R = q;
   }else{
       R->next = q;
       R = q;
   }
}

void out(node *&L){
   node *p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

void Delete_Back(node *&L){
   if(L == NULL) return;
   if(L->next == NULL){
       delete L;
       return;
   }
   node *p = L, *q;
   while (p->next->next != NULL) p = p->next;
   q = p -> next;
   p->next = NULL;
   delete q;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int x, y;
   cin >> n >> x;
   for(int i = 1; i <= n; i++){
       cin >> y;
       IS(L, y);
   }
   Delete_Back(L);
   out(L);
   return 0;
}

/*
   Cho dãy N số, X;
   Xoá nút đứng liền sau nút có giá trị là X trong trong danh sách.
*/

#include<bits/stdc++.h>

using namespace std;

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

node * L = NULL;

void IS(node *&L, int u){
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q;
       R = q;
   } else{
       R->next = q;
       R = q;
   }
}

node *find(node *L, int u){ // trả về node thứ u của danh sách
   node *p = L;
   while(p != NULL && p->data != u) p = p->next;
   return p;
}

void X_dele(node *&L, int x){
   node * p = find(L, x);
   if (L == NULL) return;
   if (p->next == NULL) return; //không có phần tử sau p
   node * q;
   q = p->next;
   p->next = q->next;
   delete q;
}

void out(node *&L){
   node * p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int n;
   int x;
   cin >> n;
   for(int i = 1; i <= n; i++){
       cin >> x;
       IS(L, x);
   }
   out(L);
   cout << '\n';
   cin >> x;
   X_dele(L, x);
   out(L);
   return 0;
}

// Cho N, phân tích N thành tích các thừa số nguyên tố

#include<bits/stdc++.h>

using namespace std;

int n;

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

node * L = NULL;

void IS(node *&L, int u){ // queue
   node *q, *R;
   q = new node;
   q->data = u;
   q->next = NULL;
   if(L == NULL){
       L = q;
       R = q;
   } else{
       R->next = q;
       R = q;
   }
}

void get(){
   int tmp;
   for(int i = 2; i <= n; i++){
       tmp = 0;
       while(n % i == 0){
           tmp++;
           n /= i;
       }
       if(tmp >= 1) for(int j = 1; j <= tmp; j++) IS(L, i);
   }
}

void printList(node *&L){
   node *p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cin >> n;
   get();
   printList(L);
   return 0;
}

// Cho số nguyên dương N, đổi N sang hệ nhị phân

#include<bits/stdc++.h>

using namespace std;

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

node * L = NULL;

void IS(node *&L, int u){ // stack
   node * q;
   q = new node;
   q->data = u;
   q->next = L;
   L = q;
}

void printfList(node *&L){
   node *p = L;
   while(p != NULL){
       cout << p->data << ' ';
       p = p->next;
   }
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   int n;
   cin >> n;
   while(n > 0){
       IS(L, n%2);
       n /= 2;
   }
   printfList(L);
   return 0;
}

// Kiểm tra biểu thức ngoặc đúng

#include<bits/stdc++.h>

using namespace std;

struct node{
   char data;
   node * next;
};

node * L = NULL;

void IS(node *&L, int u){ // stack
   node * q;
   q = new node;
   q->data = u;
   q->next = L;
   L = q;
}

bool empty(node *&L){
   return (L == NULL);
}

void pop(node * &L)
{
   if (L == NULL) return; //Nếu L rỗng, thì thoát không làm gì
   node * p = L;
   L = L->next; //Chuyển con trỏ sang nút kề phải
   delete p; //Xoá nút đầu tiên
}

bool check(string s){
   for(int i = 0; i < s.size(); i++){
       if(s[i] == '(') IS(L, s[i]);
           else{
               if(empty(L)){
                   return false;
                   break;
               } else pop(L);
           }
   }
   return empty(L);
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   string s;
   cin >> s;
   cout << check(s);
   return 0;
}

/*
    Cho dãy N số và K.
    -Tạo cây nhị phân tìm kiếm dãy trên
    -Hãy cho biết khóa K có trong danh sách hay không?
*/

#include<bits/stdc++.h>

using namespace std;

int n, k;

struct node{
    int data;
    node *left, *right;
};

// struct ch{
//    node *head;
//    node *finish;
// };

node * L = NULL;

void IS(node *&L, int u){ // thêm phần tử vào cây nhị phân tìm kiếm
    if(L == NULL){ // nếu cây rỗng
        node *q = new node;
        q->data = u;
        q->left = NULL;
        q->right = NULL;
        L = q;
    } else { // cây khác rỗng
        if(L->data > u) IS(L->left, u);
            else if(L->data < u) IS(L->right, u);
    }
}

bool search1(node * T, int k){ // đệ qui
    if(T == NULL) return false;
        else{
            if(T->data > k) return search1(T->left, k);
                else if(T->data == k) return true;
                    else return search1(T->right, k);
        }
}

bool search2(node * T, int k){ // tìm trên cây nhị phân
    node * p = T;

    while(p != NULL){
        if(p->data < k) p = p->right;
            else if(p->data == k) break;
                else p = p->left;
    }
   
    return (p != NULL);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int x;

    cin >> n >> k;;
    for(int i = 1; i <= n; i++){
        cin >> x;
        IS(L, x);
    }
   
    cout << search1(L, k) << '\n';
    cout << search2(L, k);

    return 0;
}

/*
    Cho dãy N số nguyên và K.
        -Tạo cây nhị phân tìm kiếm lưu dãy trên
        -Hãy duyệt cây theo thứ tự trước
*/

#include<bits/stdc++.h>

using namespace std;

int n;

struct node{
    int data;
    node *left, *right;
};

node * L = NULL;

void IS(node *&L, int u){
    if(L == NULL){
        node * q = new node;
        q->data = u;
        q->left = NULL;
        q->right = NULL;
        L = q;
    } else{
        if(L->data > u) IS(L->left, u);
            else if (L->data < u) IS(L->right, u);
    }
}

void Preorder (node * T){
    // Nếu cây rỗng thì không làm gì
    if (T != NULL){ // cây khác rỗng
        cout << T->data << ' '; // Xử lí nút thăm
        Preorder (T -> left); // Duyệt cây con trái
        Preorder (T -> right); // Duyệt cây con phải
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int x;

    cin >> n;
    for(int i = 0; i <= n; i++){
        cin >> x;
        IS(L, x);
    }

    Preorder(L);

    return 0;
}

/*
    Cho dãy N số nguyên và K.
        -Tạo cây nhị phân tìm kiếm lưu dãy trên
        -Hãy duyệt cây theo thứ tự trước
        -Hãy duyệt cây theo thứ tự giữa
        -Hãy duyệt cây theo thứ tự sau
*/

#include<bits/stdc++.h>

using namespace std;

int n;

struct node{
    int data;
    node *left, *right;
};

node * L = NULL;

void IS(node *&L, int u){
    if(L == NULL){
        node * q = new node;
        q->data = u;
        q->left = NULL;
        q->right = NULL;
        L = q;
    } else{
        if(L->data > u) IS(L->left, u);
            else if (L->data < u) IS(L->right, u);
    }
}

void pre_order (node * T){
    // Nếu cây rỗng thì không làm gì
    if (T != NULL){ // cây khác rỗng
        cout << T->data << ' '; // Xử lí nút thăm
        pre_order (T->left); // Duyệt cây con trái
        pre_order (T->right); // Duyệt cây con phải
    }
}

void mid_order(node * T){
    // Nếu cây rỗng thì không làm gì
    if(T != NULL){
        mid_order(T->left);
        cout << T->data << ' ';
        mid_order(T->right);
    }
}

void rear_order(node * T){
    if(T != NULL){
        rear_order(T->left);
        rear_order(T->right);
        cout << T->data << ' ';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int x;

    cin >> n;
    for(int i = 0; i <= n; i++){
        cin >> x;
        IS(L, x);
    }

    pre_order(L);
    cout << '\n';

    mid_order(L);
    cout << '\n';
   
    rear_order(L);
    return 0;
}

/*
    Cho dãy N số nguyên.
        -Tạo BinarySearch Tree lưu dãy trên
        -Tìm khóa nhỏ nhất của cây (khóa nhỏ nhất của cây là khóa cực trái)
        -Tìm khóa lớn nhất của cây (khóa lớn nhất của cây là khóa cực phải)
*/

#include<bits/stdc++.h>

using namespace std;

int n;

struct node{
    int data;
    node *left, *right;
};

node *L = NULL;

void IS(node *&L, int u){
    if(L == NULL){
        node * q = new node;
        q->data = u;
        q->left = NULL;
        q->right = NULL;
        L = q;
    } else{
        if(L->data < u) IS(L->right, u);
            else if(L->data > u) IS(L->left, u);
    }
}

// Minnode: là node cực trái

node * min_node1(node *L){ // đệ qui
    if(L->left == NULL) return L; 
    min_node1(L->left);
}

node * min_node2(node *L){ // lặp
    node * p = L;
    while(p != NULL) p = p->left;
    return p;
}

// maxnode: là node cực phải

node * max_node1(node *L){ // đệ qui
    if(L->right == NULL) return L; 
    max_node1(L->right);
}

node * max_node2(node *L){ // lặp
    node * p = L;
    while(p != NULL) p = p->right;
    return p;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int x;

    cin >> n;
    for(int i = 0; i <= n; i++){
        cin >> x;
        IS(L, x);
    }

    // node * t = min_node1(L);
    // cout << t->data;

    cout << min_node1(L)->data << '\n';
    cout << min_node2(L)->data << '\n';
    cout << max_node1(L)->data << '\n';
    cout << max_node2(L)->data << '\n';

    return 0;
}