数据结构单链表合并主程序

合并两个单链表的主程序如下所示：

#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;

// 定义单链表的结点结构
typedef struct Node
{
    ElemType data;
    struct Node *next;
} Node, *LinkList;

// 初始化单链表
void InitList(LinkList *L)
{
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
}

// 头插法建立单链表
void CreateList(LinkList *L, ElemType *arr, int n)
{
    int i;
    Node *s;
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    for (i = 0; i < n; i++)
    {
        s = (Node *)malloc(sizeof(Node));
        s->data = arr[i];
        s->next = (*L)->next;
        (*L)->next = s;
    }
}

// 合并两个单链表
void MergeList(LinkList *L1, LinkList *L2, LinkList *L3)
{
    Node *p1, *p2, *p3, *s;
    p1 = (*L1)->next;
    p2 = (*L2)->next;
    p3 = (*L3);
    while (p1 != NULL && p2 != NULL)
    {
        if (p1->data <= p2->data)
        {
            s = p1;
            p1 = p1->next;
        }
        else
        {
            s = p2;
            p2 = p2->next;
        }
        s->next = p3->next;
        p3->next = s;
        p3 = s;
    }
    p3->next = p1 ? p1 : p2;
}

// 打印单链表
void PrintList(LinkList L)
{
    Node *p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main()
{
    LinkList L1, L2, L3;
    int n1, n2;
    ElemType *arr1, *arr2;
    int i;

    printf("请输入第一个单链表的长度: ");
    scanf("%d", &n1);
    arr1 = (ElemType *)malloc(sizeof(ElemType) * n1);
    printf("请输入第一个单链表的元素: ");
    for (i = 0; i < n1; i++)
    {
        scanf("%d", &arr1[i]);
    }
    InitList(&L1);
    CreateList(&L1, arr1, n1);
    printf("第一个单链表为: ");
    PrintList(L1);

    printf("请输入第二个单链表的长度: ");
    scanf("%d", &n2);
    arr2 = (ElemType *)malloc(sizeof(ElemType) * n2);
    printf("请输入第二个单链表的元素: ");
    for (i = 0; i < n2; i++)
    {
        scanf("%d", &arr2[i]);
    }
    InitList(&L2);
    CreateList(&L2, arr2, n2);
    printf("第二个单链表为: ");
    PrintList(L2);

    InitList(&L3);
    MergeList(&L1, &L2, &L3);
    printf("合并后的单链表为: ");
    PrintList(L3);

    return 0;
}