结构推理 阅读下列算法,指出算法A的功能和时间复杂性 PROCEDURE A (h,g:pointer); (h,g分别为单循环链表(single linked circular list)中两个结点指针) PROCEDURE B(s,q:pointer); VAR p:pointer; BEGIN p:=s; WHILE p^.next<>q DO p:=p^.next; p^.next:=s; END;(of B) BEGIN B(h,g); B(g,h); END;(of A)
【正确答案】该算法功能是将原单循环链表分解成两个单循环链表:其一包括结点h到结点g的前驱结点;另一个包括结点g到结点h的前驱结点。时间复杂度是O(n)。
【答案解析】