两个非降序链表的并集,例如将链表1->2->3 和 2->3->5 并为 1->2->3->5,只能输出结果,不能修改两个链表的数据。
#include
#include
typedef int DataType;
typedef struct node
{
DataType data;
struct node *next;
}*LinkList, *pNode;
LinkList GetEmptyList()
{
LinkList head = (pNode)malloc(sizeof(struct node));
head->data = 0;
head->next = 0;
return head;
}
int AddNode(LinkList head, DataType data)
{
pNode newnode,p = head;
while(p->next) {
if(p->next->data == data) return 0;
if(p->next->data > data) {
newnode = (pNode)malloc(sizeof(struct node));
newnode->data = data;
newnode->next = p->next;
p->next = newnode;
return 1;
}
p = p->next;
}
p->next = (pNode)malloc(sizeof(struct node));
p->next->data = data;
p->next->next = 0;
return 1;
}
LinkList MergeList(LinkList LA, LinkList LB) { // 合并LA、LB到新表
LinkList head;
pNode p,q,t;
int flag;
head = p = GetEmptyList();
for(q = LA->next; q; q = q->next) {
p->next = (pNode)malloc(sizeof(struct node));
p->next->data = q->data;
p = p->next;
}
p->next = 0;
for(p = LB->next; p; p = p->next) { // 合并
flag = 1;
for(q = head; q->next && flag; q = q->next) {
if(p->data == q->next->data) flag = 0;
else if(p->data < q->next->data) {
t = (pNode)malloc(sizeof(struct node));
t->data = p->data;
t->next = q->next;
q->next = t;
flag = 0;
}
}
if(flag) {
q->next = (pNode)malloc(sizeof(struct node));
q->next->data = p->data;
q->next->next = 0;
}
}
return head;
}
void Show(LinkList head) {
pNode p = head->next;
while(p) {
printf("%d ",p->data);
p = p->next;
}
printf("\n");
}
int main()
{
DataType x;
LinkList LA = GetEmptyList();
LinkList LB = GetEmptyList();
LinkList LC;
printf("");
while(scanf("%d",&x) == 1)
{
AddNode(LA,x);
AddNode(LB,x);
printf("");
}
LC = MergeList(LA,LB);
Show(LC);
return 0;
}
怎么好像不可以,怎么优化一下?