两个不带头结点的有序单链表LA和LB的合并,请合并到LA表中再输出,LB表的空间全部释放
时间: 2024-06-13 14:04:36 浏览: 96
严版课后习题重点算法.docx
题目要求将两个有序单链表LA和LB合并到LA中,并释放LB的空间。具体实现方法如下:
1. 首先判断LA和LB是否为空,若其中一个为空,则直接返回另一个链表。
2. 定义三个指针pa、pb、pc,分别指向LA、LB、新链表的当前最后一个结点。
3. 比较pa和pb所指向结点的值的大小,将较小的结点插入到新链表中,并将pc指向该结点。
4. 重复步骤3,直到pa或pb为空。
5. 将剩余的结点插入到新链表中。
6. 将LA的头结点释放,并将新链表的头结点作为LA的新头结点。
7. 释放LB的所有结点。
具体实现代码如下:
```
void MergeList(LinkList &LA, LinkList &LB) {
if (LA == NULL) {
LA = LB;
LB = NULL;
return;
}
if (LB == NULL) {
return;
}
LNode *pa = LA, *pb = LB, *pc = LA;
while (pa != NULL && pb != NULL) {
if (pa->data < pb->data) {
pc->next = pa;
pc = pa;
pa = pa->next;
} else {
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa ? pa : pb;
LA = LA->next;
free(pc);
free(LB);
}
```
阅读全文