数据结构，链表的操作

Question

题目：如何将两个有序链表合成为一个有序链表？
问题：如图，合并后好像是乱序的，不是有序，这是哪里错了啊？求改正

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

#define ElemType int

//单链表结构
typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode,*LinkList;

//初始化
void InitList(LinkList& L)
{
    L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL)
        printf("ERROR!");
    L->next = NULL;
}

//头插法
void HeadCreate_L(LinkList& L, int n)
{
    for (int i = n; i > 0; i--)
    {
        LinkList newNode = (LinkList)malloc(sizeof(LNode));
        printf("请输入第%d个元素：", n - i + 1);
        scanf_s("%d", &newNode->data);
        newNode->next = L->next;
        L->next = newNode;
    }
}

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


//合并算法
void MergeList_L(LinkList& La, LinkList& Lb)
{
    LinkList pa = La->next;
    LinkList pb = Lb->next;
    LinkList pc = La;
    while (pa && pb )
    {
        if (pa->data <= pb->data)
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
        pc->next = pa ? pa : pb;
        free(Lb);
}
int main()
{
    int num;
    LinkList La, Lb;
    InitList(La);
    InitList(Lb);
    //创建链表La
    printf("请输入创建链表La元素个数：");
    scanf_s("%d", &num);
    HeadCreate_L(La, num);
    printf("链表La为：");
    PrintList(La);
    //创建链表Lb
    printf("请输入创建链表Lb元素个数：");
    scanf_s("%d", &num);
    HeadCreate_L(Lb, num);
    printf("链表Lb为：");
    PrintList(Lb);
    //合并到Lc
    MergeList_L(La, Lb);
    printf("合并后的链表为：");
    PrintList(La);
}

Answer 1

因为链表是降序的，所以将void MergeList_L(LinkList& La, LinkList& Lb)函数里第55行：if (pa->data <= pb->data) 修改为：if (pa->data > pb->data)j即可，供参考：

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

#define ElemType int

//单链表结构
typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode,*LinkList;

//初始化
void InitList(LinkList& L)
{
    L = (LinkList)malloc(sizeof(LNode));
    if (L == NULL)
        printf("ERROR!");
    L->next = NULL;
}

//头插法
void HeadCreate_L(LinkList& L, int n)
{
    for (int i = n; i > 0; i--)
    {
        LinkList newNode = (LinkList)malloc(sizeof(LNode));
        printf("请输入第%d个元素：", n - i + 1);
        scanf_s("%d", &newNode->data);
        newNode->next = L->next;
        L->next = newNode;
    }
}

//打印链表
void PrintList(LinkList L)
{
    LinkList p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
 
 
//合并算法
void MergeList_L(LinkList& La, LinkList& Lb)
{
    LinkList pa = La->next;
    LinkList pb = Lb->next;
    LinkList pc = La;
    while (pa && pb )
    {
        if (pa->data > pb->data)  //if (pa->data <= pb->data) 修改
        {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        }
        else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
}
int main()
{
    int num;
    LinkList La, Lb;
    InitList(La);
    InitList(Lb);

    //创建链表La
    printf("请输入创建链表La元素个数：");
    scanf_s("%d", &num);
    HeadCreate_L(La, num);
    printf("链表La为：");
    PrintList(La);

    //创建链表Lb
    printf("请输入创建链表Lb元素个数：");
    scanf_s("%d", &num);
    HeadCreate_L(Lb, num);
    printf("链表Lb为：");
    PrintList(Lb);

    //合并到Lc
    MergeList_L(La, Lb);
    printf("合并后的链表为：");
    PrintList(La);
    return 0;
}