5.假设某个单向循环链表的长度大于1,且表中既无头结点也无头指针。已知s 为指向链表中某个结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。
时间: 2023-05-30 08:05:47 浏览: 64
如果链表的长度小于等于1或者s为NULL,则无法删除前驱结点,直接返回。
否则,先找到s所指向的结点的前驱结点pre和后继结点next。如果s指向的是第一个结点,则pre为链表的最后一个结点;如果s指向的是最后一个结点,则next为链表的第一个结点。
然后,将pre的next指针指向next,并释放原来的s所指向的结点。
最后,如果s指向的是第一个结点,则将链表的头指针指向next;如果s指向的是最后一个结点,则将链表的尾指针指向pre。
具体实现如下:
```C++
void deletePreNode(node* s) {
if (s == NULL || s->next == s) { // 链表长度小于等于1或者s为NULL,无法删除前驱结点
return;
}
node* p = s->next; // p指向s的后继结点
node* q = s; // q指向s
while (q->next != s) { // 找到s的前驱结点
q = q->next;
}
node* pre = q; // pre指向s的前驱结点
node* next = p; // next指向s的后继结点
while (next->next != s) { // 找到s的后继结点
next = next->next;
}
pre->next = next; // 删除pre的后继结点,将pre的next指针指向next
free(s); // 释放s所指向的结点
if (s == pre->next) { // 如果s指向的是第一个结点
head = next; // 将链表的头指针指向next
}
if (s == next) { // 如果s指向的是最后一个结点
tail = pre; // 将链表的尾指针指向pre
}
}
```