关于数据结构中的循环链表

Question

关于数据结构中的循环链表，为什么如果设的是头指针，对表尾进行操作需要O（n）的时间复杂度，用尾指针只需要O（1）的时间复杂度？

Answer 1

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7522196
• 你也可以参考下这篇文章：合并两个有序数组，要求时间复杂度为O（n），且只要到O（1）的辅助空间
• 除此之外, 这篇博客: 数据结构和算法：什么是数据结构，什么是算法中的 为什么算法1时间复杂度为O(n)而不是O(1)呢？ 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

•   我们先来看看算法2、3为什么时间复杂度为O(1)而不是O(3)、O(100)：

    算法3、4都很类似，不管n有多大，只要n在int的范围内，得到的结果sum也在int范围内，如算法3中：1001 + 100(100-1)1/2   和  10001 + 1000*(1000-1)*1/2、算法4中：(1 + 100) * 100 / 2  和 (1 + 10000) * 10000/ 2 得出结果sum的时间是非常接近的，几乎可以忽略不记，像这样跟n的大小无关的，执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶。

    在算法3中的int sum = n*a1 + n*(n-1)*d/2;其实可以看做先算na1（得到结果为a）、再算n-1（得到结果为c）、再算nc（得到结果为D）、再算D* d（得到结果为e）、再算 n*(n-1)*d/2（得到结果为b）、最后算a + b，结果是1+1+1+1+1+1=6次，根据推导大O阶方法，1+1+1+1+1+1其实就是1，所以这就是为什么算法3、4是1+1+1，时间复杂度为O(1)，而算法1是1+n+1，时间复杂度为O(n)。

    上面的例子介绍了常数阶O(1)和线性阶O(n)，接下来介绍对数阶O(logn)和平方阶O(n2)

• 以下回答由chatgpt基于相关博客总结生成:

  循环链表相比于普通链表，最后一个节点指向头节点，形成一种环形的结构。在进行表尾操作时，即要获取尾节点进行操作时，如果使用头指针，则需要从头遍历到最后一个节点，才能获取到尾节点，时间复杂度为O(n)；但如果使用尾指针，则可以直接通过尾指针获取尾节点，时间复杂度为O(1)。具体的例子可以结合某个具体的问题场景来说明，例如可以考虑设计一个环形队列，首节点为当前队列中尾一个元素的下一个位置，尾节点为当前队列中最后一个元素的位置，这时如果需要进行队列长度的操作，使用头指针需要遍历整个队列，而使用尾指针只需要一次操作就能获取到队列长度。