下列算法,指出算法A的功能和时间复杂度,其中h、g分别为单循环链表中两个节点指针.VoidB(int*s,int*q）{Int*p;p=s;while（p->next!=q)P=p->next;P->next=s;}VoidA(int*h,int*g){B(h,g);B(g,h);}

Question

下列算法,指出算法A的功能和时间复杂度,其中h、g分别为单循环链表中两个节点指针.
Void B(int*s,int*q）{
Int*p;
p=s;
while（p->next!=q)
P=p->next;
P->next=s;
}
Void A(int*h,int*g){
B(h,g);
B(g,h);
}

Answer 1

估计你的代码是这样的吧：
void B(int *s, int *q)
{
int *p;
p = s;
while（p->next != q)
p = p->next;
p->next = s;
}
void A(int *h, int *g)
{
B(h, g);
B(g, h);
}
首先说下函数B的作用,函数B的作用是将单循环链表（也可以是单向链表,如果是单链表,那么s节点一定要在q节点之前,题意中指的是单循环链表）中的q节点和s节点相连接（q->next = s）,从而形成一个单循环链表.
函数A的作用是使单循环链表中的g的下一个节点为h而h的下一个节点为g（即g->next = h且h->next = g）,也可以说是形成一个只有g和h节点的单循环链表.

如果g,h所在单循环链表节点数为n,则当q->next == s时,"B(h, g);"要执行最多次" p = p->next;"（n-2次）,执行p->next = s;一次；B(g, h);只执行p->next = s;一次.所以时间复杂度肯定是线性阶,即T(n) = O(n).