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

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

本文将详细讲解C语言中链表合并算法List Merge(List L1, List L2)的实现原理，并对代码中关键部分，如PtrToNode p 和 head 的作用进行深入分析，帮助读者理解代码逻辑和数据结构。

代码实现

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 是用来创建一个新链表的指针变量。

• PtrToNode p = NULL; 表示创建一个指向链表节点的指针变量p，并初始化为NULL。
• PtrToNode head = NULL; 表示创建一个指向链表头节点的指针变量head，并初始化为NULL。
• head = (PtrToNode)malloc(sizeof(struct Node)); 表示动态分配内存空间，创建一个新的节点，然后将其地址赋给head。malloc函数用于动态分配内存空间，sizeof(struct Node)表示分配的内存空间大小为一个节点的大小。
• head->Next = NULL; 表示将新节点的Next指针指向NULL，即新链表的尾节点。
• p = head; 表示将p指针指向head，即p指向新链表的头节点。

这样，p和head就分别指向了新链表的头节点，p用于遍历新链表并添加节点，head用于返回新链表的头节点。

总结

这段代码实现了链表合并算法，通过遍历两个输入链表，将节点按照数据大小顺序插入到新链表中。PtrToNode p 和 head 作为关键指针变量，分别负责遍历和返回新链表，最终得到一个排序后的合并链表。