单选题

在一个长度为 n(n>1) 的带头结点的单链表 h 上, 另设有尾指针 r(指向尾结点), 执行(     )操作与链表的长度有关。

【正确答案】 B
【答案解析】

假设单链表的头和尾两个指针分别为 h 和 r。
A 项, 操作过程如下: LNode * p=h->next; h->next=p->next; free(p);
B 项, 操作过程如下(需要找到尾结点的前一个结点的指针 p):
           LNode * p=h ;
           while(p->next!=r) p=p->next;
           p->next=NULL;
           free(r) ; r=p;
C 项, 操作过程如下(假设插入地址为 s 的结点):
           s->next=h->next;
           h->next=s;
D 项, 操作过程如下(假设插入地址为 S 的结点):
           r->next=s;
           S->next=NULL;
           r=s;
从上述过程可以看出, B 项对应算法的时间复杂度为 O(n), ACD 项对应算法的时间复杂度为 O(1)。