实现一个可以用菜单控制，用动态存储实现单链表的创建，单链表的插入，单链表的删除，单链表的查找和单链表的显示，并且可以将顺序表LA和lb的数据元素按非递减有序排列，以及将LA和lb归并为一个新的顺序表Lc而且，Lc中的元素仍然按非递减有序排列

这是一个较为复杂的题目，需要多个函数之间的协作。下面给出一个简单的实现。

#include <iostream>

using namespace std;

// 定义链表节点结构体
struct Node {
    int data;   // 数据域
    Node* next; // 指针域，指向下一个节点
};

// 创建链表
Node* createList(){
    Node* head = NULL;  // 链表头指针初始化为NULL，表示链表为空
    Node* tail = NULL;  // 链表尾指针初始化为NULL，表示尾节点还没有确定

    int x;
    cout << "请输入链表的元素，输入-1结束：" << endl;
    cin >> x;

    while (x != -1) {   // 当输入-1时停止输入
        Node* p = new Node; // 创建新的节点
        p->data = x;        // 设置节点的数据域
        p->next = NULL;     // 设置节点的指针域，指向NULL

        if (head == NULL) { // 当前链表为空，将头指针指向新节点
            head = p;
            tail = p;       // 初始化尾指针
        } else {            // 当前链表不为空，将尾指针指向新节点
            tail->next = p;
            tail = p;
        }

        cin >> x;           // 继续输入下一个元素
    }

    return head;  // 返回链表头指针
}

// 在链表中插入元素
void insertNode(Node* head) {
    int pos, x;
    cout << "请输入要插入元素的位置和数值：" << endl;
    cin >> pos >> x;

    Node* p = new Node; // 创建新节点

    p->data = x;       // 设置节点的数据域

    if (pos == 1) {    // 插入为头节点
        p->next = head;
        head = p;      // 更新头指针
    } else {           // 插入为非头节点
        Node* q = head;
        int i = 1;

        while (i < pos - 1 && q != NULL) { // 找到插入位置的前一个节点
            q = q->next;
            i++;
        }

        if (q == NULL) { // 找不到插入位置
            cout << "插入位置错误！" << endl;
        } else {
            p->next = q->next;
            q->next = p;
        }
    }

    // 输出插入后的链表
    cout << "插入后的链表为：" << endl;
    Node* q = head;

    while (q != NULL) {
        cout << q->data << " ";
        q = q->next;
    }

    cout << endl;
}

// 在链表中删除元素
void deleteNode(Node* head) {
    int pos;
    cout << "请输入要删除元素的位置：" << endl;
    cin >> pos;

    if (pos == 1) {   // 删除头节点
        head = head->next;
    } else {           // 删除非头节点
        Node* p = head;
        int i = 1;

        while (i < pos - 1 && p != NULL) { // 找到删除位置的前一个节点
            p = p->next;
            i++;
        }

        if (p == NULL || p->next == NULL) { // 找不到删除位置
            cout << "删除位置错误！" << endl;
        } else {
            Node* q = p->next;
            p->next = q->next;
            delete q;
        }
    }

    // 输出删除后的链表
    cout << "删除后的链表为：" << endl;
    Node* q = head;

    while (q != NULL) {
        cout << q->data << " ";
        q = q->next;
    }

    cout << endl;
}

// 在链表中查找元素
void searchNode(Node* head) {
    int x;
    cout << "请输入要查找的元素：" << endl;
    cin >> x;

    Node* p = head;
    int i = 1;

    while (p != NULL && p->data != x) { // 查找节点
        p = p->next;
        i++;
    }

    if (p == NULL) { // 没有找到
        cout << "查找不到该元素！" << endl;
    } else {
        cout << "该元素在链表中的位置为：" << i << endl;
    }
}

// 显示链表的元素
void displayList(Node* head) {
    cout << "链表的元素为：" << endl;
    Node* p = head;

    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }

    cout << endl;
}

// 将两个有序数组合并为一个新的有序数组
void mergeArray(int A[], int B[], int C[], int n, int m) {
    int i = 0, j = 0, k = 0;

    while (i < n && j < m) { // 依次将A和B中的较小元素加入C中
        if (A[i] <= B[j]) {
            C[k] = A[i];
            i++;
        } else {
            C[k] = B[j];
            j++;
        }

        k++;
    }

    while (i < n) { // 将A中剩余的元素加入C中
        C[k] = A[i];
        i++;
        k++;
    }

    while (j < m) { // 将B中剩余的元素加入C中
        C[k] = B[j];
        j++;
        k++;
    }
}

int main() {
    Node* head = NULL; // 链表头指针初始化为NULL
    int choice;

    do {
        cout << "请选择要进行的操作：" << endl;
        cout << "1. 创建链表" << endl;
        cout << "2. 在链表中插入元素" << endl;
        cout << "3. 在链表中删除元素" << endl;
        cout << "4. 在链表中查找元素" << endl;
        cout << "5. 显示链表中的元素" << endl;
        cout << "6. 合并两个有序数组" << endl;
        cout << "0. 退出" << endl;

        cin >> choice;

        switch (choice) {
            case 1:
                head = createList(); // 创建链表
                break;
            case 2:
                insertNode(head); // 在链表中插入元素
                break;
            case 3:
                deleteNode(head); // 在链表中删除元素
                break;
            case 4:
                searchNode(head); // 在链表中查找元素
                break;
            case 5:
                displayList(head); // 显示链表中的元素
                break;
            case 6: {
                int n, m;
                cout << "请输入数组A和数组B的元素个数：" << endl;
                cin >> n >> m;

                int A[n], B[m], C[n+m];
                cout << "请输入数组A的元素：" << endl;

                for (int i = 0; i < n; i++) {
                    cin >> A[i];
                }

                cout << "请输入数组B的元素：" << endl;

                for (int i = 0; i < m; i++) {
                    cin >> B[i];
                }

                // 将A和B合并为C，C中元素按非递减有序排列
                mergeArray(A, B, C, n, m);

                cout << "合并后的数组为：" << endl;

                for (int i = 0; i < n + m; i++) {
                    cout << C[i] << " ";
                }

                cout << endl;

                break;
            }
            case 0:
                break;
            default:
                cout << "输入的操作不存在，请重新输入！" << endl;
                break;
        }
    } while (choice != 0);

    return 0;
}