作业帮假设有两个按元素值递增有序排列的带头节点的单链表A和B.试编写算法将A表和B表归并成按一个元素值递减有序(允许值下相同)排列的线性表C,要求利用原表的节点空间存放C
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/28 01:56:41
假设有两个按元素值递增有序排列的带头节点的单链表A和B.试编写算法将A表和B表归并成按一个元素值递减有序(允许值下相同)排列的线性表C,要求利用原表的节点空间存放C
假设有两个按元素值递增有序排列的带头节点的单链表A和B.试编写算法将A表和B表归并成按一个元素值递减有序(允许值下相同)排列的线性表C,要求利用原表的节点空间存放C
假设有两个按元素值递增有序排列的带头节点的单链表A和B.试编写算法将A表和B表归并成按一个元素值递减有序(允许值下相同)排列的线性表C,要求利用原表的节点空间存放C
/* 链表节点 */
typedef struct Node {
int data;
struct Node *next;
} Node;
/* 合并两个升序链表为降序链表 */
Node *merge_lists(Node *a, Node *b)
{
Node *pa = a->next, *pb = b->next, *t;
/* 新链表的头结点使用 a 的头结点 */
a->next = NULL;
free(b); // b 的头结点是不需要的,可以释放掉
while(pa != NULL && pb != NULL) {
if(pa->data < pb->data) { // 将 pa 插入新链表头部
t = pa->next;
pa->next = a->next;
a->next = pa;
pa = t;
} else { // 将 pb 插入新链表头部
t = pb->next;
pb->next = a->next;
a->next = pb;
pb = t;
}
}
/* 注：以下两个循环只会执行其中一个 */
/* 只剩链表 a 的节点 */
while(pa != NULL) {
t = pa->next;
pa->next = a->next;
a->next = pa;
pa = t;
}
/* 只剩链表 b 的节点 */
while(pb != NULL) {
t = pb->next;
pb->next = a->next;
a->next = pb;
pb = t;
}
return a;
}
有问题请指教 :)