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

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node
{
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */

List Merge( List L1, List L2 );
List FreeList(List L); //用于链表释放
List Paixu(List L);  //用于链表排序

int main()
{
    List L1, L2, L;
    L1 = Read();
    L2 = Read();
    L = Merge(L1, L2);
    L1 = FreeList(L1); //释放L1
    L2 = FreeList(L2);  //释放L2
    Print(L);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */
List Read()
{
    PtrToNode first = NULL;

    int n;
    for (;;)
    {
        printf("Enter a series of integers (0 to terminate): ");
        scanf("%d", &n);
        if (n == 0)//当输入为0则退出循环
            break;
        PtrToNode new_node = malloc(sizeof(struct Node));
        if (new_node == NULL)
        {
            printf("Error: malloc failed in add to list\n");
            exit(0);
        }
        new_node->Data = n;
        new_node->Next = first;
        first = new_node;
    }
    return Paixu(first);
}

void Print(List L)
{
    List p;
    if (L==NULL)
        printf("NULL\n");
    else
    {
        for (p = L; p != NULL; p = p->Next)
            printf("%d ", p->Data);
        printf("\n");
    }
}

List Merge(List L1, List L2)
{
    //合并链表
    PtrToNode first = NULL;
    while (L1 != NULL)//创建并把旧链表复制到新链表
    {
        PtrToNode new_node = malloc(sizeof(struct Node));
        if (new_node == NULL)
        {
            printf("Error: malloc failed in add to list\n");
            exit(0);
        }
        new_node->Data = L1->Data;
        new_node->Next = first;
        first = new_node;
        L1 = L1->Next;
    }
    
    while (L2 != NULL)//创建并把旧链表复制到新链表
    {
        PtrToNode new_node = malloc(sizeof(struct Node));
        if (new_node == NULL)
        {
            printf("Error: malloc failed in add to list\n");
            exit(0);
        }
        new_node->Data = L2->Data;
        new_node->Next = first;
        first = new_node;
        L2 = L2->Next;
    }
    return Paixu(first);
}

List Paixu(List L)//链表排序 升序，只交换 Data
{
    int n;
    PtrToNode first = L, t;
    for (t = first; t->Next != NULL;)
    {
        if (t->Data > (t->Next)->Data)
        {
            n = t->Data;
            t->Data = (t->Next)->Data;
            (t->Next)->Data = n;
            t = first;
        }
        else
        {
            t = t->Next;
        }
    }
    return first;
}

List FreeList(List L)
{
    for (List t; L != NULL;)
    {
        t = L;
        L = L->Next;
        free(t);
    }

    return NULL;
}

[此贴子已经被作者于2017-9-22 20:34编辑过]

这个代码显然不能满足19楼的题意要求：
1，题意要求先输入链表节点数再输入相应数目的节点值，你直接是提示输入以0结束链表输入。
2，题意要求“应直接使用原序列中的结点”，应该理解为不是产生新的链表节点，而是应该在L1、L2已有节点上合并成一个递增系列的链表
3，裁判测试程序错误。裁判测试程序中的合并函数声明是“List Merge( List L1, List L2 );”，如果这个代码不能更改的话，则执行该函数是不能将指针L1、L2的值置NULL的，只有将函数声明修改为“List Merge( List *L1, List *L2 );”或“List Merge( List &L1, List &L2 );”.当然，对于根本不检查函数参数类型是否一致的codeblock也许可以强行做到，但不提倡这样做。

嗯,22楼说出了宝贵的参考建议在此之上久久还可以补充一下~记得这题有点像我们上课的练习多项式相加~不过感觉这就是合并应该会比那简单一点~提示一下在两个链表寻找两个当前链表的最大值作为链表前驱指针~通常情况下合并链表的路径有点像蛇形迂回曲折这样的……只要其中一个链表走完如果另一个链表为非空的话勾上另一个链表的数据就可以啦~当然这前提是原链表本来是有序的~

而且19楼代码提示代码结构里面应该不用出现malloc这东东~
PS:不过还是要理解一下19楼输出提示的NULL是怎么来的~

[此贴子已经被作者于2017-9-22 23:51编辑过]

多谢指正
其实我也知道不符合题意，因为耗费了我太多时间，所以我就乱改题目了

第1点确实应该修改，也很容易实现，比如输入N，然后一个for(i=0;i<N;i++)循环就可以，我最后懒得改了
如果第二点按要求做的话，就像你说的，L1 L2 作为形参，没办法修改L1 L2指向的内存，我一开始是直接把L1的尾节点指向L2的头结点，然后用排序那个函数，这样做可以保留原来的节点，但是L1和L2 不能赋值NULL，也就是输出不会是NULL，除非在函数外直接赋值NULL，或者像我写这个，创建一个新链表，然后把旧的释放掉