C语言实现两个递增链表合并为一个非递减链表

本题可以使用双指针法来实现。定义两个指针p1和p2分别指向链表L1和L2的头结点，然后比较p1和p2所指向的结点的数据大小，将较小的结点接到结果链表的末尾，并将指针p1或p2后移一位，直到其中一个链表为空。然后将剩余的链表接到结果链表的末尾。最后返回结果链表的头指针。

具体实现如下：

List Merge(List L1, List L2) {
    List result = (List)malloc(sizeof(struct Node));  // 创建结果链表的头结点
    result->Next = NULL;
    List p1 = L1->Next;  // 指针p1指向L1的第一个结点
    List p2 = L2->Next;  // 指针p2指向L2的第一个结点
    List cur = result;  // 指针cur指向结果链表的当前结点

    // 遍历两个链表，将较小的结点接到结果链表的末尾
    while (p1 && p2) {
        if (p1->Data <= p2->Data) {
            cur->Next = p1;
            p1 = p1->Next;
        } else {
            cur->Next = p2;
            p2 = p2->Next;
        }
        cur = cur->Next;
    }

    // 将剩余的链表接到结果链表的末尾
    if (p1) {
        cur->Next = p1;
    }
    if (p2) {
        cur->Next = p2;
    }

    // 将L1和L2的头结点释放掉
    free(L1);
    free(L2);

    return result->Next;
}

需要注意的是，返回结果链表的头指针时，应该是指向结果链表的第一个结点，而不是头结点。所以在创建结果链表的头结点时，应该将其Next指针初始化为NULL。而返回结果链表的头指针时，应该返回result->Next。

另外，在释放L1和L2的头结点时，应该使用free函数进行释放。

完整代码如下：

#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);


int main()
{
    List L1, L2, L;

    L1 = Read();
    L2 = Read();

    L = Merge(L1, L2);

    Print(L);
    Print(L1);
    Print(L2);

    return 0;
}


List Merge(List L1, List L2)
{
    List result = (List)malloc(sizeof(struct Node));  // 创建结果链表的头结点
    result->Next = NULL;
    List p1 = L1->Next;  // 指针p1指向L1的第一个结点
    List p2 = L2->Next;  // 指针p2指向L2的第一个结点
    List cur = result;  // 指针cur指向结果链表的当前结点

    // 遍历两个链表，将较小的结点接到结果链表的末尾
    while (p1 && p2) {
        if (p1->Data <= p2->Data) {
            cur->Next = p1;
            p1 = p1->Next;
        } else {
            cur->Next = p2;
            p2 = p2->Next;
        }
        cur = cur->Next;
    }

    // 将剩余的链表接到结果链表的末尾
    if (p1) {
        cur->Next = p1;
    }
    if (p2) {
        cur->Next = p2;
    }

    // 将L1和L2的头结点释放掉
    free(L1);
    free(L2);

    return result->Next;
}


List Read()
{
    int n;
    scanf("%d", &n);
    List head = (List)malloc(sizeof(struct Node));  // 创建头结点
    head->Next = NULL;
    List tail = head;  // 指针tail指向链表的最后一个结点

    for (int i = 0; i < n; i++) {
        List node = (List)malloc(sizeof(struct Node));  // 创建新结点
        scanf("%d", &(node->Data));
        node->Next = NULL;
        tail->Next = node;  // 将新结点接到链表的末尾
        tail = node;  // 更新tail指针
    }

    return head;
}


void Print(List L)
{
    if (L->Next == NULL) {
        printf("NULL\n");
        return;
    }

    List p = L->Next;  // 指针p指向链表的第一个结点

    while (p) {
        printf("%d ", p->Data);
        p = p->Next;
    }
    printf("\n");
}