单向循环链表的时间复杂度

单向循环链表的时间复杂度如下：

1. 插入操作：在单向循环链表的某个位置插入一个节点，时间复杂度为 O(1)，因为只需要修改前一个节点的指针即可。

2. 删除操作：删除单向循环链表中的某个节点，时间复杂度为 O(1)，因为只需要修改前一个节点的指针即可。

3. 查找操作：查找单向循环链表中的某个节点，需要遍历整个链表，时间复杂度为 O(n)，其中 n 为节点的总数。

因此，单向循环链表的插入和删除操作的时间复杂度为 O(1)，而查找操作的时间复杂度为 O(n)。

相关问题

假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

由于是单向循环链表，无法直接访问前驱结点。因此，需要遍历整个链表，找到s的前驱结点，并将其删除。

具体实现步骤如下：

1. 定义一个指针p，初始指向s所指向的结点。

2. 从p开始遍历整个链表，直到找到p的前驱结点。

3. 在遍历过程中，定义一个指针q，始终指向p的前一个结点。

4. 如果p遍历到链表的末尾，即p指向的结点为链表的尾结点，则q指向的结点为链表的头结点。

5. 将q所指向的结点从链表中删除即可。

具体实现代码如下：

void deletePreNode(Node* s) {
    Node* p = s;
    Node* q = NULL;
    while (p->next != s) {
        q = p;
        p = p->next;
    }
    if (q == NULL) { // s的前驱结点为链表的尾结点，q指向头结点
        q = p;
        while (q->next != p) {
            q = q->next;
        }
    }
    q->next = p->next;
    free(p);
}

注意，此算法的时间复杂度为O(n)，其中n为链表的长度。因此，如果链表很长，效率可能较低，建议考虑其他实现方式。

若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表（不含头结点）

可以很方便地实现这些操作。在插入结点时，只需要将新结点插入到尾结点之后，然后更新尾指针即可；在删除尾结点时，只需要找到尾结点的前一个结点，将其指向头结点，然后更新尾指针即可。这种链表的优点是插入和删除操作的时间复杂度都是 O(1)，缺点是无法快速访问链表中间的结点。