【数据结构/C语言】有序单链表L1、L2合并

1.根据输入的n和n个递增的有序数据建立一个带头结点的有序单链表L1，并输出有序链表中各元素值;
2.根据输入的m和m个递增的有序数据建立一个带头结点的有序单链表L2，并输出有序链表中各元素值;
3.将有序链表L1和L2合并到单链表L1中，要求使用原链中的结点，并使L1保持其原有序性，最后输出合并后的有序链表中各结点的元素值。

#pragma warning (disable:4996)
#include <stdio.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef struct  LNode
{
    ElemType data;
    struct LNode* next;
} LNode, * LinkList;

Status L_Creat(LinkList& L, int n)
{
    LinkList r;
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    r = L;
    printf("请输入各元素值:\n");
    for (int i = 0; i < n; i++)
    {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        if (!p)
            return ERROR;
        scanf("%d", &p->data);
        p->next = NULL;
        r->next = p;
        r = p;
    }
    return OK;
}

Status L_Insert(LinkList& L, int i, ElemType e)
{
    LinkList p = L, s;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        ++j;
    }
    if (!p || j > i - 1)
        return ERROR;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}
Status L_Delete(LinkList& L, int i, ElemType& e)
{
    LinkList p = L, q;
    int j = 0;
    while (p->next && j < i - 1)
    {
        p = p->next;
        ++j;
    }
    if (!p->next || j > i - 1)
        return ERROR;
    q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return OK;
}
Status L_Search(LinkList L, int i, ElemType& e)
{
    LinkList  p = L->next;
    int  j = 1;
    while (p && j < i)
    {
        p = p->next;
        j++;
    }
    if (!p || j > i)
        return ERROR;
    e = p->data;
    return OK;
}

void L_Display(LinkList L)
{
    LinkList p = L->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
Status Merge(LinkList& L1, LinkList& L2)
{
    LinkList p = L1->next, q = L2->next, r;
    L1->next = NULL;
    r = L1;
    while (p && q)
    {
        if (p->data <= q->data)
        {
            r->next = p;
            r = p;
            p = p->next;
        }
        else
        {
            r->next = q;
            r = q;
            q = q->next;
        }
    }
    if (p)
        r->next = p;
    else
        r->next = q;
    free(L2);     
    return  OK;
}// Merge
int main()
//主函数 
{
    LinkList L;
    int n, i;
    ElemType x;
    printf("请输入链表长度:");
    scanf("%d", &n);
    L_Creat(L, n);
    printf("这个链表是:\n");
    L_Display(L);

    printf("请输入你想插入的位置:");
    scanf("%d", &i);
    printf("请输入你想要插入的元素:");
    scanf("%d", &x);
    L_Insert(L, i, x);
    printf("插入之后的链表是:");
    L_Display(L);

    printf("请输入你想删除的位置:");
    scanf("%d", &i);
    L_Delete(L, i, x);
    printf("删除的元素是:%d\n", x);
    printf("删除之后的链表是:");
    L_Display(L);

    printf("请输入待查找元素的位置:");
    scanf("%d", &i);
    if (L_Search(L, i, x))
        printf("第%d个元素是:%d\n", i, x);
    else
        printf("第%d个元素不存在\n", i);

    LinkList L1, L2;
    int a, b;
    printf("请输入L1的链表长度:");
    scanf("%d", &a);
    L_Creat(L1, a);
    printf("L1链表为:\n");
    L_Display(L1);
    printf("请输入L2的链表长度:");
    scanf("%d", &b);
    L_Creat(L2, b);
    printf("L2链表为:\n");
    L_Display(L2);
    if(Merge(L1, L2));
    printf("L1,L2合并后:");
    L_Display(L1);
    return 0;
}

原文地址：http://www.cnblogs.com/aal-izz-well-eureka/p/16813212.html