题目

设线性表 A=(a1, a2, ..., am)，B=(b1, b2,..., bn) ，试写一个按下列规则合并
A，B为线性表 C的算法，即使得
C = (a1, b1,..., am, bm, bm+1,..., bn) 当 m <= n 时；

C= (a1, b1,..., an, bn, an+1, ..., am) 当 m >= n 时；
线性表 A，B和 C均以单链表作存储结构，且 C表利用 A表和 B 表中的结点空间构成。注意：单链表的长度值 m和 n 均未显式存储。

分析

可以看出，不论是 A 的长度长还是 B 的长度长，最终 C 链表中的首元结点都是 A 链表的首元结点，所以只需要让 C = A 即可。

本算法的大致方法就是多次插入，即：将 B 链表中的元素插入 A 链表中，最后再处理一下长度的问题即可。

处理长度可以利用如下思路：

当 A 链表长度大时直接正常插入就行(因为 B 链表长度较短，所以当循环到大于 B 链表之后就是单纯的遍历 A 链表的剩下节点)；

当 B 链表长度大时，循环完成之后需要将 A 链表的最后一个节点的 next 指向 B 链表剩下的节点。

代码：

初始化：

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

#define OK 1
#define ERROR 0

typedef int ElemType;
typedef int Status;

typedef struct LNode 
{                 
    ElemType data;
    LNode *next;
}LNode, *LinkList;

Status InitList(LinkList &L)
{   // 初始化单链表 L
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;

    return OK;
}//InitList

创建单链表：

Status CreateList(LinkList &L, int e)
{   // 创建单链表，将新元素 e 放入单链表 L 中
    LinkList p, temp;
    p = L;
    temp = (LinkList)malloc(sizeof(LNode));
    while(p->next)
        p = p->next;
    temp->data = e;
    temp->next = NULL;
    p->next = temp;

    return OK;
}//CreateList

打印单链表：

Status DispList(LinkList &L)
{   // 打印单链表 L
    LinkList p;
    p = L->next;
    while(p)
    {
        printf("%d\t", p->data);
        p = p->next;
    }
    return OK;
}//DispList

合并单链表：

Status ListMarge(LinkList &A, LinkList &B, LinkList &C)
{
    LinkList pa, pb, qa, qb;
    pa = A->next;  // pa 指向 A 的首元结点
    pb = B->next;
    C = A;        // 因为 C 中第一个元素是 A 中的元素，所以只需要 C 指向 A就行了
    while(pa && pb)
    {
        qa = pa;
        qb = pb;
        pa = pa->next;
        pb = pb->next;
        qb->next = qa->next;
        qa->next = qb;
    }
    if(!pa)  // 如果 A 链表的长度小于 B 链表的长度
        qb->next = pb; // 将 B 的后续节点连接到新链表的尾端
    pb = B;  // 准备删除 B 链表
    free(pb);

    return OK;
}//ListMerge

主函数：

int main()
{
    LinkList A, B, C;
    InitList(A);    InitList(B);   InitList(C);
    // 向 A 中添加元素
    for(int i = 1; i < 6; i ++)
        CreateList(A, i);
    // 向 B 中添加元素
    for(int j = 1; j < 7; j ++)
        CreateList(B, j);
    // 分别打印三个单链表
    printf("\n单链表 A 为:\n");
    DispList(A);   
    printf("\n单链表 B 为：\n");
    DispList(B);   
    printf("\n单链表 C 为：\n");
    DispList(C);
    // 合并
    ListMarge(A, B, C);
    printf("\n合并后的单链表 C 为：\n");
    DispList(C);

    return OK;

}

在主函数中可以看出，创建单链表 A 、B 时，A 的长度小于 B 的长度，所以它的合并示意图为：

“连接”的详细顺序已经标注在图中了。

值得一提的是：

在单链表的插入操作中，我们都是看到这样的操作步骤：

q->data = e; // 待插入节点的 data 域
q->next = p->next;  // 将待插入节点的 next 与 p 的直接后继节点相连
p->next = q;     // 将 q 作为 p 的直接后继节点

那为什么不能是这样的操作顺序呢：

q->data = e; // 待插入节点的 data 域
p->next = q;     // 将 q 作为 p 的直接后继节点
q->next = p->next;  // 将待插入节点的 next 与 p 的直接后继节点相连

因为当我们先将 q 作为 p 的直接后继节点时，接下来的 q->next = p->next; 会造成 q->next = q; 没错！q 指向其本身！

THE END!

原文链接：https://blog.csdn.net/qq_41109668/article/details/104657085