ZEKEGU1997 2019-07-22 21:54 采纳率: 0%
浏览 2036
已采纳

带头结点的循环/非循环单链表删除开始结点的时间复杂度

  • 数据结构的辅导书上答案是两个都是O(1).
  • 我觉得循环单链表要找到最后一个结点，把最后一个指针指向新的开始结点，所以，时间复杂度应该是O(n)。 是不是我哪里想错了呢？
  • 写回答

3条回答 默认 最新

  • ZEKEGU1997 2019-07-22 23:52
    关注

    带头结点的循环单链表是尾结点是指向头结点的，删除开始结点不影响，所以不需要遍历，时间复杂度为O(1)
    不带头结点的循环单链表尾结点是指向开始结点的，这时候需要遍历,为O(n)

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题？