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

3个回答

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

时间复杂度是O(1),不需要一次遍历

qq_43533956
ZEKEGU1997 我明白了谢谢
10 个月之前 回复
qq_43533956
ZEKEGU1997 循环单链表的终端结点不是要指向开始结点吗
10 个月之前 回复
qq_43533956
ZEKEGU1997 那“找到最后一个结点,把最后一个指针指向新的开始结点"这样操作的问题在哪呢
10 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐