假设有一个长度大于 1 的循环单链表,表中既无头节点也无头指针,已知 s 为指向链表 中某个节点的指针,试编写算法,在链表中删除指针 s 指向的结点(需预先创建符合要 求的循环单链表)。
时间: 2024-02-05 21:13:23 浏览: 77
这道题需要注意的是,由于循环单链表没有头节点和头指针,无法通过遍历找到待删除节点的前驱节点。因此我们可以先把待删除节点的值和下一个节点的值交换,然后删除下一个节点即可。
具体的算法步骤如下:
1. 首先判断链表是否为空,如果为空则直接返回。
2. 如果链表不为空,从指针 s 开始,遍历链表,找到指向待删除节点的前驱节点 p。
3. 将待删除节点和 p 的后继节点交换值。
4. 删除 p 的后继节点。
下面是具体的代码实现:
```
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
void deleteNode(ListNode* s) {
if (s == NULL) return; // 链表为空,直接返回
ListNode *p = s; // 初始化 p 指针为 s
while (p->next != s) {
p = p->next;
} // 找到待删除节点的前驱节点 p
ListNode *tmp = s->next; // 保存待删除节点的后继节点
s->val = tmp->val; // 将待删除节点的值更新为后继节点的值
s->next = tmp->next; // 将待删除节点的后继指针指向后继节点的后继节点
free(tmp); // 释放后继节点的内存空间
}
```
需要注意的是,如果待删除节点是链表的最后一个节点,那么上述算法会出错。因此我们需要先特判一下这种情况。
阅读全文