假设有一个长度大于 1 的循环单链表,表中既无头节点也无头指针,已知 s 为指向链表 中某个节点的指针,试编写算法,在链表中删除指针 s 指向的结点(需预先创建符合要 求的循环单链表)。C语言代码
时间: 2024-02-05 18:13:29 浏览: 15
假设循环单链表的节点结构体定义如下:
```c
typedef struct ListNode {
int val;
struct ListNode *next;
} ListNode;
```
算法思路:
1. 如果链表为空,则直接返回;
2. 如果要删除的节点是头节点,则需要找到链表的尾节点,将尾节点的 next 指针指向头节点的下一个节点,同时释放头节点;
3. 如果要删除的节点不是头节点,则需要找到该节点的前一个节点 prev,将 prev 的 next 指针指向要删除节点的下一个节点,同时释放要删除的节点。
C语言代码实现如下:
```c
void deleteNode(ListNode *s) {
if (s == NULL) return; // 链表为空,直接返回
ListNode *prev = s, *cur = s->next;
while (cur != s) { // 找到要删除节点的前一个节点 prev
prev = cur;
cur = cur->next;
}
if (s == prev) { // 要删除的是头节点
while (prev->next != s) prev = prev->next; // 找到尾节点
prev->next = s->next; // 将尾节点的 next 指针指向头节点的下一个节点
free(s); // 释放头节点
} else { // 要删除的不是头节点
prev->next = s->next; // 将 prev 的 next 指针指向要删除节点的下一个节点
free(s); // 释放要删除的节点
}
}
```