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

C语言链表合并算法详解：List Merge(List L1, List 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;
}

代码解析：

这段代码实现了将两个有序链表L1和L2合并成一个新的有序链表的功能。

• PtrToNode p = NULL; 和 PtrToNode head = NULL;

这两行代码定义了两个指针变量p和head，它们都是指向链表节点的指针。

• p： 用于遍历链表，并在合并过程中连接节点。
• head： 用来保存合并后链表的头节点。

代码中的其他关键点：

• p1 = L1->Next; 和 p2 = L2->Next;： 分别将p1和p2指向链表L1和L2的第一个节点。
• head = (PtrToNode)malloc(sizeof(struct Node));： 创建一个新的节点作为合并后链表的头节点，并将head指向它。
• while(p1 != NULL && p2 != NULL)： 当两个链表都还有节点时，循环执行合并操作。
• if(p1->Data <= p2->Data)： 如果L1的当前节点数据小于等于L2的当前节点数据，则将L1的当前节点连接到合并链表的尾部，并移动p1指针指向下一个节点。否则，将L2的当前节点连接到合并链表的尾部，并移动p2指针指向下一个节点。
• p = p->Next;： 将p指针指向下一个节点，以便在循环中继续连接节点。
• 最后将剩余的节点连接到合并链表的尾部，并返回合并后链表的头节点。

通过以上代码，我们可以将两个有序链表合并成一个新的有序链表，并在合并过程中保证新链表仍然是有序的。