问道题，王道队列习题，假设循环单链表表示的队列长度为n，队头固定在链表表尾，若只设头指针，则进队时间复杂度为（ ）
王道上说答案是O（n）
但是如果我往头指针后面插入一个节点，形成循环，然后交换data内容，不就等于往前插了个节点吗，然后再头指针指向新节点，不就是完成了进队操作吗，这难道不是常数复杂度吗?
头指针说的应该是指向队头的指针，循环链表作队列那头节点前面的应该就是队尾了，我应该没理解错吧，总不能头指针说的是链表头吧

我是这么理解的，这里没有说链表里的data是一个数字或字符
假设data是一个长度为m的数组，那么复杂度就是 O(m) 了 所以 O(1)并不准确
这个题目我一开始也选了 O(1)，百思不得其解，看了题解才知道 “头指针”是链表头指针，我以为是队列头指针。。

答案的意思就是头指针是链表的头指针，但题干并没有明确说明。

你应该概念混了 首先队列只能在队尾插
它这里rear肯定指向的是一个首结点不是头结点，链表尾结点一般不可能定义为头结点形式
1.如果你在rear指向的首结点前面插入一个新结点，交换值，这个符合在对尾操作，但是你可以拿到rear指向的首结点前一个元素的地址吗，你要将这个结点的next设为你新插入结点地址
2.假如你在首结点（不是头结点）后面插入新结点，你就是在队列头操作了，违背队列原则
综上你要拿到当前首结点前那一个元素地址，也就是队列尾指针（循环单链表的倒数第二个），O(N)

头指针： 这里是链表的表头L， 不是队列的front
这里已知L，交换数据只能实现在front后， 即L前插入， 无法实现front前的插入

插入是在队尾插入，队列长度为n，链表长度未知。
头指针指向表头，表头存的是队列第二个元素，链表的n-1个节点存队尾的元素，在队尾插入即在链表的n个节点赋值。
找到的n个节点，时间复杂度为O(n)，赋值时间复杂度为O(1)。进队时间复杂度为O(n)。

链表的长度可以理解为队列的最大长度。往头指针后面插入一个节点增加了链表的长度，改变了队列长度，所以不可取。
（另：链表为循环链表，链表的最后一个节点指向链表的首节点。插入节点后新节点成为的链表的首节点，此时应该使链表的尾节点指向首节点。要使尾节点指向首节点首先要找到尾节点，后将尾节点指向新节点，该操作的时间复杂度为O(x)，x为链表长度。需要注意的是此操作是在队列的第一个元素后插入新元素。）

我觉得先进先出，两端操作就叫队列

插错地方了

所以是默认队列在链表里存储不能逆置吗，就是a3指向a2，a2指向a1这样。我以为头指针L指向的元素是队尾元素

我不明白他的队头固定在链表尾是什么意思，队列头不应该在表头吗，如果在表尾那跟在表尾进行插入冲突啊，而且表尾一直在变，麻了看不懂

楼里全是讨论头指针位置的 ，只有我懂楼主，有标准解释了吗

这里的头指针到底是对链表而言还是对队列而言呀

楼主的意思就是把这个链表的头指针当做一个循环队列的表尾指针，从链表头每插入一个新节点，就让头指针指向这个新节点。时间复杂度为O(1)。但是你忽略了这是一个循环单链表，必须将链表的尾结点的指针域指向新插入的结点，这才完成了进队的所有操作，找到尾结点需要O(n)

题目中只给了指向链头的头指针（注意队头指针跟队尾指针是没给的，不能自己加上）