假设在长度大于1的单循环链表中,既无头结点也无头指针。s为指向链表中某个结点的指针,试编写算法删除结点*s的直接前趋结点。
时间: 2023-04-26 13:06:04 浏览: 118
算法如下:
1. 如果链表为空或者只有一个结点,则无法删除直接前趋结点,直接返回。
2. 如果*s指向头结点,则需要先找到链表的尾结点,将尾结点的next指针指向头结点的next指针,然后将头结点删除即可。
3. 如果*s指向尾结点,则需要先找到尾结点的前驱结点,将前驱结点的next指针指向头结点,然后将尾结点删除即可。
4. 如果*s指向中间的某个结点,则需要先找到*s的前驱结点和前驱结点的前驱结点,将前驱结点的next指针指向*s的next指针,然后将*s删除即可。
算法实现如下:
void deletePredecessor(Node* s) {
if (s == NULL || s->next == NULL) {
return;
}
Node* p = s;
while (p->next != s) {
p = p->next;
}
if (s == p) { // s指向头结点
Node* tail = p->next;
while (tail->next != s) {
tail = tail->next;
}
tail->next = s->next;
delete s;
} else if (s->next == p) { // s指向尾结点
p->next = s->next;
delete s;
} else { // s指向中间的某个结点
Node* q = s;
while (q->next != s) {
q = q->next;
}
q->next = s->next;
delete s;
}
}