Question

求数据结构的题目答案……

1：已知带头结点的单链表L中的结点按整数值递增排列，试写一算法，将值为X的结点插入表L中，使得L仍然有序，并分析算法的时间复杂度。
2：已知两个单链表A和B分别表示两个集合，其元素递增有序，编写一个函数求出A和B得交集C，要求C同样以元素递增的单链表形式储存。

Answer 1

if(!head.next) head.next=x;
else
{
if(x.d<=head.next.d) {x.next=head.next;head.next=x;}
else
{
p=head;
while(p.next && p.next.d>x.d)
{
p=p.next;
}
x.next=p.next;
p.next=x;
}
}

时间复杂度为O(n)

2.
假设链表带头结点
createList(C);
pA=A.head.next;
pB=B.head.next;
pC=C.head;
while(pA && pB)
{
temp=new node;
temp.next=NULL;
if(pA.d<=pB.d)
{temp.d=pA.d;pA=pA.next;}
else
{temp.d=pB.d;pB=pB.next;}
pC.next=temp;
pC=pC.next;
}
while(pA)
{
temp=new node;
temp.d=pA.d;
temp.next=NULL;
pC.next=temp;
pC=pC.next;
}
while(pB)
{
temp=new node;
temp.d=pB.d;
temp.next=NULL;
pC.next=temp;
pC=pC.next;
}