题26

题26

题目

Q:设有一个长度为 的循环单链表,若从表中删除首元结点的时间复杂度达到 , 则此时采用的循环单链表的结构可能是 ( ).
A. 只有表头指针, 没有头结点
B. 只有表尾指针, 没有头结点
C. 只有表尾指针, 带头结点
D. 只有表头指针, 带头结点

分析

A:什么是首元节点？
也就是第一个节点，第一个有效的节点，不能是dummy node，值域里面要有值
肯定没有表尾节点，要是有表尾节点，又是循环的，那么可以O1访问头结点
有没有头结点在这里有什么关系？

解

A
在循环单链表中, 删除首元结点后, 要保持链表的循环性, 因此需要找到首元结点的前驱。
当链表带头结点时, 其前驱就是头结点, 因此不论是表头指针还是表尾指针, 删除首元结点的时间都为 。
当链表不带头结点时,其前驱是尾结点,因此,若有表尾指针,就可在 的时间找到尾结点;
若只有表头指针,则需要遍历整个链表找到尾结点,时间为 。