C语言实现两个递增链表合并算法

本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。

函数接口定义

List Merge( List L1, List L2 );

其中 List 结构定义如下：

typedef struct Node *PtrToNode;

struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};

typedef PtrToNode List; /* 定义单链表类型 */

L1 和 L2 是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数 Merge 要将 L1 和 L2 合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。

裁判测试程序样例

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


/* 你的代码将被嵌在这里 */

输入样例

输出样例

1 2 3 4 5 6 8 10 
NULL
NULL

实现思路

首先，我们需要创建一个新的链表来存储合并后的结果。我们可以先创建一个空的头节点，然后从两个链表的第一个节点开始比较大小，将较小的节点添加到新链表中，并将指针指向下一个节点。重复这个过程直到其中一个链表为空，然后将另一个链表剩余的节点添加到新链表的末尾。最后返回新链表的头节点即可。

代码实现

List Merge( List L1, List L2 )
{
    // 创建一个空的头节点
    List head = (List)malloc(sizeof(struct Node));
    head->Next = NULL;
    List current = head;

    // 比较两个链表的节点大小，并将较小的节点添加到新链表中
    while (L1 && L2) {
        if (L1->Data <= L2->Data) {
            current->Next = L1;
            L1 = L1->Next;
        } else {
            current->Next = L2;
            L2 = L2->Next;
        } 
        current = current->Next;
    }
    
    // 将剩余的节点添加到新链表的末尾
    if (L1) {
        current->Next = L1;
    }
    if (L2) {
        current->Next = L2;
    }
    
    // 返回新链表的头节点
    return head->Next;
}

注意事项

注意：在合并链表之后，原始的两个链表 L1 和 L2 将为空链表。所以在测试程序中打印它们时会输出 NULL。

总结

通过以上代码实现，我们成功地将两个递增排序的链表合并成了一个非递减的整数序列。该算法思路清晰，易于理解和实现，并且在实际应用中也具有广泛的应用场景。