#include <stdio.h>
#include <stdlib.h>

typedef int EmenType;

typedef struct Node {
    int data;
    struct Node *next;

    Node() {
        next = NULL;
    }
} node, *Link;

bool Init(Link head);

bool Insert(Link, int i, EmenType e);

bool Delete(Link p, int i, EmenType &e);

void print(Link p);

void MergeList(Link la, Link lb, Link lc);

int main() {
    Link head;
    head = (Link) malloc(sizeof(node));
    head->next = NULL;
    Init(head);
    Insert(head, 2, 100);
    Link tmp = head;
    print(tmp);
    int a;
    Delete(head, 2, a);
    print(head);
    Link heada = (Link) malloc(sizeof(node));
    Link headb = (Link) malloc(sizeof(node));
    Link headc = (Link) malloc(sizeof(node));
    Init(heada);
    Init(headb);
    MergeList(heada, headb, headc);
    print(headc);
}

void MergeList(Link heada, Link headb, Link headc) {
    headc->data = -1;
    while (heada && headb) {
        if (heada->data <= headb->data) {
            headc->next = heada;
            headc = heada;
            heada = heada->next;
        } else {
            headc->next = headb;
            headc = headb;
            headb = headb->next;
        }
    }
    headc->next = heada ? heada : headb;
    free(headb);
}

void print(Link p) {
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

bool Delete(Link p, int i, EmenType &e) {
    int j = 0;
    while (j < i - 1 && p) {
        ++j;
        p = p->next;
    }
    if (!p || j > i - 1) {
        return false;
    }
    Link q = (Link) malloc(sizeof(node));
    q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return true;
}

bool Insert(Link p, int i, EmenType e) {
    int j = 0;
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p || j > i + 1) {
        return false;
    }
    Link s = (Link) malloc(sizeof(node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

bool Init(Link head) {
    bool flag = true;
    Link p = head;
    p->next = NULL;
    for (int i = 0; i < 5; i++) {
        if (flag) {
            p->data = i;
            flag = false;
            continue;
        }
        Link s = (Link) malloc(sizeof(node));
        s->data = i;
        s->next = NULL;
        s->next = p->next;
        p->next = s;
        p = s;
    }
    return true;
}