在长度为n的()上，删除第一个元素，其算法的时间复杂度为O(n)

刺骨的言语ヽ痛彻心扉 2023-07-22 03:46 61阅读 0赞

在长度为n的（）上，删除第一个元素，其算法的时间复杂度为O(n)  
A.只有表头指针的不带表头结点的循环单链表  
B.只有表尾指针的不带表头结点的循环单链表  
C.只有表尾指针的带表头结点的循环单链表  
D.只有表头指针的带表头结点的循环单链表

答案：A

分析：  
单链表只能按单方向顺序访问节点，按题目意思，只有当**A条件**时，并当新元素的节点从**表头插入**，使得第一个元素的节点在表尾，才成立。这样表头指针顺序访问节点，访问至链表尾部时，复杂度刚好为O(n)。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70]  
对于B而言，不带头节点循环链表，表尾指针，**如果是头插法**则第一元素就是表尾指针rear（假设表尾指针为rear）所指的节点，即当前节点，时间复杂度为O(1)。**如果是正常顺序插入节点**（即非头插法），由于是循环链表，表尾指针rear指向最后一个元素，rear->next即为第一个元素（因为循环链表，表尾的next是表头，且没有头节点），时间复杂度仍然是O(1)，所以B不成立。  
对于C而言，和B情况相似，多了一个表头节点，**如果是头插法**，则和B一样表尾指针rear所指当前元素即为第一个元素，时间复杂度为O(1)。**如果是正常顺序插入节点**，则比B多一个头节点，就变成rear->next->next，但时间复杂度仍然是O(1)，所以C不成立。  
对于D而言，比A多一个头节点，虽然当头插法时时间复杂度为O(n+1)，根据次数化解原则，就为O(n)，但是答案不是选D（我也不是很清楚，老师讲解时直接跳过没有解释清楚，希望大佬评论解答，感激！！！）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjY3ODI5MA_size_16_color_FFFFFF_t_70]: /images/20230528/3268ae1d2d364e55948b429a2c256c92.png