假设有一个长度大于 1 的循环单链表,表中既无头节点也无头指针,已知 s 为指向链表 中某个节点的指针,试编写算法,在链表中删除指针 s 指向的结点(需预先创建符合要 求的循环单链表)
时间: 2023-12-14 07:36:10 浏览: 62
数据结构算法 习题 答案 带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针).pdf
5星 · 资源好评率100%
删除循环单链表中的指定节点有以下几种情况:
1. 待删除节点是头节点:需要找到链表中的尾节点,将尾节点的 next 指针指向头节点的下一个节点,然后删除头节点即可。
2. 待删除节点是尾节点:需要找到待删除节点的前一个节点,将其 next 指针指向头节点,然后删除尾节点即可。
3. 待删除节点在链表中间:需要找到待删除节点的前一个节点,将其 next 指针指向待删除节点的下一个节点,然后删除待删除节点即可。
下面是具体的实现代码:
```
void deleteNode(Node* s) {
if (s == NULL) { // 指针为空,直接返回
return;
}
Node *p = s;
while (p->next != s) { // 找到待删除节点的前一个节点
p = p->next;
}
if (s == p) { // 待删除节点是头节点
p = p->next;
while (p->next != s) { // 找到尾节点
p = p->next;
}
p->next = s->next;
delete s;
} else if (s->next == NULL) { // 待删除节点是尾节点
p->next = NULL;
delete s;
} else { // 待删除节点在链表中间
p->next = s->next;
delete s;
}
}
```
需要注意的是,这里的链表是循环单链表,需要特殊处理头节点和尾节点。同时,我们需要判断待删除节点是否为空,若为空直接返回,避免出现未定义行为。
阅读全文