C语言实现链表合并算法：List Merge(L1, L2)

这段代码实现了两个有序链表 L1 和 L2 的合并操作，并返回一个新的有序链表。

List Merge( List L1, List L2 )
{
    PtrToNode p1 = L1->Next;
    PtrToNode p2 = L2->Next;
    PtrToNode p = NULL;
    PtrToNode head = NULL;
    if(p1 == NULL)
        return L2;
    if(p2 == NULL)
        return L1;
    head = (PtrToNode)malloc(sizeof(struct Node));
    head->Next = NULL;
    p = head;
    while(p1 != NULL && p2 != NULL)
    {
        if(p1->Data <= p2->Data)
        {
            p->Next = p1;
            p1 = p1->Next;
        }
        else
        {
            p->Next = p2;
            p2 = p2->Next;
        }
        p = p->Next;
    }
    if(p1 != NULL)
        p->Next = p1;
    if(p2 != NULL)
        p->Next = p2;
    L1->Next = NULL;
    L2->Next = NULL;
    return head;
}

指针作用

• PtrToNode p 和 head: 用来对合并后的链表进行遍历和构建的指针。
• head: 合并后链表的头指针，通过动态内存分配 malloc 来创建一个新的节点，并将其指针赋值给 head。然后将 head 的 Next 指针设置为 NULL，表示这是最后一个节点。
• p: 用来追踪当前合并链表的最后一个节点，开始时 p 指向 head。
• PtrToNode p1 和 p2: 用来遍历链表 L1 和 L2 的指针，分别指向链表 L1 和 L2 的第一个节点，开始时跳过头节点。

代码解析

1. 首先判断两个链表是否为空，如果其中一个为空，直接返回另一个链表。
2. 使用 malloc 分配内存空间创建一个新的节点作为合并后的链表的头节点，并初始化其 Next 指针为 NULL。
3. 使用 while 循环遍历两个链表，比较 p1 和 p2 节点的 Data 值的大小，将较小的节点链接到 p 的 Next 指针上，并将 p1 或 p2 指针向后移动一位。然后将 p 指针向后移动一位，以指向新加入的节点。
4. 当其中一个链表遍历完毕后，将另一个链表中剩余的节点直接链接到 p 的 Next 指针上。
5. 最后将原始链表 L1 和 L2 的 Next 指针设置为 NULL，表示它们已经不再是合并后的链表的一部分，并返回合并后的链表头指针 head。

通过以上步骤，就完成了两个有序链表的合并操作，并将合并后的链表返回。