已知2个递增无序的单链表A,B分别存储了一个集合,请设计算法实现这2个集合的并集,

Question

已知2个递增无序的单链表A,B分别存储了一个集合,请设计算法实现这2个集合的并集,

Answer 1

递增无序?递增有序吧,如果无序,首先给两个链表排序,以下代码按升序合并
先剔除两条链表里的相同值,然后再合并
LinkList ElimtList(LinkList L)/* L为空头 *//* 剔除相同值 */
{
LinkList p = NULL;
LinkList t = NULL;
LinkList tmp = NULL;
p = L->next; /* 保存结点2 */
t = p->next; /* 保存结点3 */
while (NULL != t)/* 进入循环 */
{
if (p->num == t->num)
{
tmp = t->next;/* 保存结点t的下一个结点 */
p->next = tmp;/* 结点t的上一个结点与下一个结点相接 */
free(t); /* 释放结点t */
t = tmp; /* t指向下一个结点 */
}
else
{
p = p->next;/* 后移一位 */
t = t->next;/* 后移一位 */
}
}
return(L);
}
LinkList MergeList(LinkList L1,LinkList L2)/* 合并L1,L2两个链表,用的地址L1作为新链表地址返回 *//* 合并 */
{
LinkList p = NULL;
LinkList p1 = NULL;
LinkList p2 = NULL;
LinkList tmp = NULL;
p = L1;
p1 = L1->next;
p2 = L2->next;
while ((NULL != p1) && (NULL != p2))
{
if (p1->num < p2->num)/* 若p1的值小于p2的值,p1后移1位,p2不动 */
{
p = p1;
p1 = p1->next;
}
else if (p1->num > p2->num)/* 若p1的值大于p2的值,则p1前插入p2,p2后移1位,p1不动 */
{
tmp = p2->next;
p2->next = p1;
p->next = p2;
p = p2;
p2 = tmp;
}
else/* if (p1->num == p2->num) */
{
tmp = p2->next;/* 保存结点p2的下一个结点 */
free(p2); /* 释放结点p2 */
p2 = tmp; /* p2指向下一个结点 */
}
}
p->next = p1 p1 :p2; /*插入剩余段*/
free(L2); /*释放L2的头节点*/
return(L1);
}