两个递增的线性表合成一个递增的线性表

可以使用归并排序的思想，将两个递增的线性表按顺序合并成一个新的递增的线性表。具体的做法可以使用双指针来遍历两个线性表，比较当前指针指向的元素大小，选择较小的元素加入新的线性表中，直到其中一个线性表遍历结束，然后将另一个线性表中剩余的元素全部加入新的线性表中即可。

相关问题

用线性表将两个递增的线性表合并成一个非递减线性表，要求利用原表的结点空间结构构造新表

算法思路：

1.定义两个指针分别指向两个递增的线性表的头结点；
2.新建一个空的线性表作为合并后的结果；
3.比较两个指针指向结点的大小，将小的结点插入新表中；
4.将小的结点的指针向后移动一位；
5.重复执行3、4两步，直到其中一个表的指针指向空；
6.将另一个表剩余的结点插入新表中；
7.返回合并后的结果。

实现代码如下（C语言）：

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

typedef struct Node{
    int data;
    struct Node *next;
}Node, *LinkedList;

LinkedList createList(int n) {  // 创建一个长度为n的有序线性表
    LinkedList head = (LinkedList)malloc(sizeof(Node));
    head->next = NULL;
    LinkedList p = head;
    int i;
    for (i = 0; i < n; i++) {
        LinkedList newNode = (LinkedList)malloc(sizeof(Node));
        scanf("%d", &newNode->data);
        newNode->next = NULL;
        p->next = newNode;
        p = p->next;
    }
    return head;
}

LinkedList mergeList(LinkedList l1, LinkedList l2) {  // 合并两个有序线性表
    LinkedList head = (LinkedList)malloc(sizeof(Node));
    head->next = NULL;
    LinkedList p = head;
    LinkedList p1 = l1->next;
    LinkedList p2 = l2->next;
    while (p1 != NULL && p2 != NULL) {
        if (p1->data <= p2->data) {
            p->next = p1;
            p1 = p1->next;
        } else {
            p->next = p2;
            p2 = p2->next;
        }
        p = p->next;
    }
    if (p1 == NULL) {
        p->next = p2;
    } else {
        p->next = p1;
    }
    return head;
}

void printList(LinkedList list) {  // 输出链表中的元素
    LinkedList p = list->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    int n, m;
    printf("请输入有序线性表1的长度：");
    scanf("%d", &n);
    printf("请输入有序线性表1的元素：");
    LinkedList l1 = createList(n);
    printf("请输入有序线性表2的长度：");
    scanf("%d", &m);
    printf("请输入有序线性表2的元素：");
    LinkedList l2 = createList(m);
    printf("合并后的非递减线性表为：");
    LinkedList l3 = mergeList(l1, l2);
    printList(l3);
    return 0;
}

运行结果：

请输入有序线性表1的长度：3
请输入有序线性表1的元素：1 3 5
请输入有序线性表2的长度：4
请输入有序线性表2的元素：2 4 6 8
合并后的非递减线性表为：1 2 3 4 5 6 8

已知l1和l2为两个线性表，l1的各个数据递增排列，l2的各个数据也递增排列。两个线性表中的数据各不相同，请通过归并的方法将这两个线性表合并为一个线性表，要求合并后的线性表数据递增排列。

可以使用归并排序的思想来合并这两个线性表。具体步骤如下：

1. 定义一个新的线性表l3，用于存放合并后的结果。

2. 定义三个指针：p1指向l1的第一个元素，p2指向l2的第一个元素，p3指向l3的第一个元素。

3. 比较p1和p2所指向的元素大小，将较小的元素插入到l3中，并将指向该元素的指针向后移动一位。

4. 重复步骤3，直到p1或p2指向了线性表的末尾。

5. 将剩余的元素依次插入到l3中。

6. 返回l3作为合并后的结果。

需要注意的是，由于l1和l2中的数据各不相同，因此在比较两个元素大小时，不能简单地使用等于号，而应该使用小于号或大于号。