合并代码讲解

第一步，为了定义链表的结构，需要创建一个节点结构体。

typedef struct lnode {int data; // 节点存储的数据struct lnode *next; // 指向下一个节点的指针
} lnode, *linklist;

解释: 此结构体lnode代表链表的节点，包含一个整数型数据data和一个指向下一个节点的指针next。linklist是指向lnode的指针，用于表示链表。

第二步，为了合并两个链表，需要编写合并函数的原型。

void merge(linklist L1, linklist L2);

解释: merge函数接受两个参数，L1和L2，它们是两个链表的头节点指针。函数的目的是将L2中的所有节点合并到L1中。

第三步，为了合并两个链表，需要初始化指针以遍历两个链表。

lnode *p1 = L1->next, *p2 = L2->next, *r, *tail;

解释: p1和p2分别初始化为指向L1和L2的首节点（第一个实际的数据节点）。r用于临时存储下一个节点的指针，而tail用于跟踪合并后链表的最后一个节点。

第四步，为了合并两个链表，需要遍历两个链表并按顺序合并。

while (p1 && p2) {if (p1->data <= p2->data) {r = p1->next;p1->next = L1->next; // 将p1接到L1的前面L1->next = p1; // L1的下一个节点是p1p1 = r; // p1移动到下一个节点} else {r = p2->next;p2->next = L1->next; // 将p2接到L1的前面L1->next = p2; // L1的下一个节点是p2p2 = r; // p2移动到下一个节点}
}

解释: 使用一个循环来遍历两个链表，比较当前节点的数据，将较小数据的节点接在L1的前面，然后移动对应的指针到下一个节点。

第五步，为了合并两个链表，需要处理剩余节点。

if (p1) p2 = p1; // 如果p1还有剩余节点，将它们接到L1的末尾
while (p2) {r = p2->next;p2->next = L1->next;L1->next = p2;p2 = r;
}

解释: 如果一个链表在合并过程中先结束，则将另一个链表的剩余部分直接连接到L1的前面。

第六步，为了合并两个链表，需要释放第二个链表的内存。

free(L2); // 释放L2的头结点

解释: 合并完成后，需要释放L2链表的头结点内存。

完整代码：

void merge(linklist &L1,linklist &L2)
{lnode *p1=L1->next,*p2=L2->next,*r;L1->next=NULL;while(p1&&p2){if(p1->data<=p2->data){r=p1->next;p1->next=L1->next;L1->next=p1;p1=r;}else{r=p2->next;p2->next=L1->next;L1->next=p2;p2=r;}}if(p1) p2=p1;while(p2){r=p2->next;p2->next=L1->next;L1->next=p2;p2=r;}free(L2);
}