合并线性表 描述：已知两非递减的顺序线性表，要求合并成一个新的非递减顺序线性表。 输入：输入包含四行，第一行为自然数n，表示第一个非递减顺序线性表的长度，第二行为n个自然数构成的非递减顺序线性表，第三行为自然数m，表示第二个非递减顺序线性表的长度，第四行为m个自然数构成的非递减顺序线性表。 输出：用一行输出合并后的非递减顺序线性表，各数之间用一个空格隔开。 样例输入： 2 1 3 3 2 3 6 样例输出： 1 2 3 3 6

以下是一种基于归并排序思想的合并线性表的算法：

1. 定义两个指针i和j，分别指向两个线性表的起始位置。

2. 比较i和j位置上的元素，将较小的元素添加到合并后的线性表中，并将指向该元素的指针向后移动一位。

3. 重复步骤2，直到其中一个线性表的所有元素都添加完毕。

4. 将另一个线性表中剩余的元素全部添加到合并后的线性表中。

5. 输出合并后的线性表。

具体实现如下：

#include <iostream>
using namespace std;

const int MAXN = 100000;

int A[MAXN], B[MAXN], C[MAXN];

int main() {
    int n, m, i, j, k;
    cin >> n;
    for(i=0;i<n;i++) {
        cin >> A[i];
    }
    cin >> m;
    for(j=0;j<m;j++) {
        cin >> B[j];
    }
    i = j = k = 0;
    while(i < n && j < m) {
        if(A[i] < B[j]) {
            C[k++] = A[i++];
        } else {
            C[k++] = B[j++];
        }
    }
    while(i < n) {
        C[k++] = A[i++];
    }
    while(j < m) {
        C[k++] = B[j++];
    }
    for(i=0;i<k;i++) {
        cout << C[i] << " ";
    }
    cout << endl;
    return 0;
}

时间复杂度为O(n+m)，空间复杂度为O(n+m)。