用单循环链表表示长度为n的链表队列，如只存在尾指针，则完成入

[单选题]

用单循环链表表示长度为n的链表队列，如只存在尾指针，则完成入队和出队的时间复杂度是（）

查看答案及解析

Shepherdeen

1楼能说人话吗？单循环链表就是一个【单向环】而已，入队表示从头进，出队表示从尾出。。。。

若只有头指针，瞬间入队，入队复杂度就是O（1），但是出队的话要从头走到尾走n个结点，指针才能到尾部，出队复杂度就是O(n)！

若只有尾指针，瞬间出队，出队复杂度就是O（1），由于单向环首位相连，从尾指针下一位就是头指针了！故而入队复杂度也是O（1）

发表于 2021-11-09 13:32:29 回复(1)

华电美男

用单循环链表表示长度为n的链表队列，若只设置头指针，则出队和入队的时间复杂度分别是O(1)、O(n)；若只设置头指针，则出队和入队的时间复杂度分别是O(1)、O(1)；

发表于 2020-08-10 16:08:09 回复(1)

提交观点

问题信息

小米集团测试开发工程师 2020

上传者：小小

难度：

2条回答 37收藏 3510浏览

扫一扫，把题目装进口袋