假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。
时间: 2023-05-31 18:02:31 浏览: 126
由于是单向循环链表,无法直接访问前驱结点。因此,需要遍历整个链表,找到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为链表的长度。因此,如果链表很长,效率可能较低,建议考虑其他实现方式。
阅读全文