#include<iostream>

using namespace std;

class Node {
public:
    int data;
    Node* next;
    
};

class Link {//链表类
public:
    Node* head;
    Link()//创造一个头结点
    {
        head = new Node();
        head->next = NULL;
    }
    void nizhi()//头插法实现链表的逆置
    {
        Node* p = head->next;//保存首元结点位置
        head->next = NULL;//清空链表
        Node* temp = p->next;//temp指向p的后继结点
        while (temp!= NULL) {
            p->next = head->next;
            head->next = p;//头插操作
            p = temp;
            temp = p->next;
        }

        p->next = head->next;//插入最后一个结点
        head->next = p;
    }

    void charu(int n,Node *p)//在指定位置插入
    {
        int count = 1;
        Node* pre = head;//创建一个pre指针，保存指定位置结点的前驱
        while (pre->next != NULL&&count!=n) {
            pre = pre->next;
            count++;
        }
        p->next = pre->next;//插入操作
        pre->next = p;
    }

    int find(int m)//查找某个元素，返回它的位置
    {
        int count = 1;//记录元素位置
        Node* p = head->next;
        while (p != NULL) {
            if (p->data == m) {
                return count;
            }
            p = p->next;
            count++;
        }
        if (p == NULL) {
            cout << "Not Found" << endl;
            return -1;
        }
    }

    void shanchu(int n)//在指定位置删除
    {
        int count = 1;
        Node* pre = head;//记录指定位置结点的前驱
        Node* cur = head->next;
        if (cur == NULL) {
            cout << "链表为空" << endl;
            return;
        }
        while (pre->next != NULL && count != n) {
            pre = pre->next;
            cur = cur->next;
            count++;
        }
        pre->next = cur->next;//删除操作
        delete cur;
    }

    void tailadd(Node* p)//尾插法（创建链表时常用）
    {
        Node* q = head;
        while (q->next != NULL) {
            q = q->next;
        }
        q->next = p;
        p->next = NULL;
    }
    void headadd(Node *p)//头插法（创建链表时常用）
    {
        p->next = head->next;
        head->next = p;
    }
};

int main()
{
    //创建单链表la
    int n1;
    cin >> n1;
    Link* la = new Link();
    for (int i = 0; i < n1; i++) {
        Node* p = new Node();
        cin >> p->data;
        la->tailadd(p);
    }
    Node* p = new Node();
    //在指定位置插入元素
        int m, n;
        cin >> m >> n;//m是元素,n是位置
        Node* p1 = new Node();
        p1->data = m;
        la->charu(n, p1);
        //遍历输出链表元素
        p = la->head->next;
        while (p != NULL) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
        //删除指定位置的元素
        cin >> n;
        la->shanchu(n);
        //遍历输出链表元素
        p = la->head->next;
        while (p != NULL) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
        //查找某个元素的位置
        cin >> m;
        cout << la->find(m) << endl;
        //实现链表的逆置
        la->nizhi();
        p = la->head->next;
        while (p != NULL) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
        //创建单链表lb
        int n2;
        cin >> n2;
        Link* lb = new Link();
        for (int i = 0; i < n2; i++) {
            Node* p = new Node();
            cin >> p->data;
            lb->tailadd(p);
        }
        //合并单链表
        Node* pa = la->head->next;
        Node* pb = lb->head->next;
        Link* lc = new Link();
        Node* pc = lc->head;//新链表的工作指针
        while (pa != NULL && pb != NULL) {
            if (pa->data < pb->data) {
                /*pc->next = pa;
                pc = pa;*/

                Node* temp = pa->next;//设置一个temp指向pa的后继，原因是尾插之后，pa->next会指向空，从而和后面断开联系
                lc->tailadd(pa);
                pa = temp;
            }
            else {
                Node* temp = pb->next;
                lc->tailadd(pb);
                pb = temp;
            }
        }
        while (pa != NULL) {
            Node* temp = pa->next;
            lc->tailadd(pa);
            pa = temp;
        }
        while (pb != NULL) {
            Node* temp = pb->next;
            lc->tailadd(pb);
            pb = temp;
        }
        //遍历输出链表元素
        p = lc->head->next;
        while (p != NULL) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    return 0;
}