假设循环单链表表示的队列长度为n，队头固定在链表表尾，若只设头指针，则进队操作的时间复杂度为（ ）。
A、O(n) B、O(1) C、O(n*2) D、O(nlog2n)
我的理解：（希望对你有所帮助~）
把题目的循环单链表改成单链表，那么进队操作是O(1)【头插法嘛，队尾在链表的头部，又有头指针，天时地利这不得是O(1)都不行】。
但是循环单链表需要使得链成环（很容易忽视的细节），入队头插新节点后要将尾部的结点的next指针更新，但是又没有指向尾结点的指针，所以还要从头到尾遍历到尾结点才行，硬生生拖成了O(n)。
这也是为什么一般用链表作为队列可以不用循环链表就不用的原因。
队头在表尾，队尾不应该在表头吗？有头结点，队尾入队，不应该是o（1）吗？不理解，
月溅星河 回复 阿拉蕾上岸： 初始队列为空的时候队头和队尾都在表尾，随着元素不断入队，队尾才向表头移动。
A 入队时需要去到链...
用户登录可进行刷题及查看答案
A 入队时需要去到链表尾部，保证成环。O(n)
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案