假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s为指向链表中某结点的指针,试编写算法在链表中删除指针s所指结点的前驱结点。
时间: 2023-04-27 16:02:41 浏览: 166
算法步骤如下:
1. 判断链表长度是否大于1,如果不是则无法删除前驱结点,直接返回。
2. 遍历链表,找到指针s所指向的结点,并记录其前驱结点和后继结点。
3. 如果指针s所指向的结点是链表的第一个结点,则将链表的尾结点的后继指针指向第二个结点,同时释放第一个结点的内存空间。
4. 如果指针s所指向的结点不是链表的第一个结点,则将其前驱结点的后继指针指向其后继结点,同时释放指针s所指向的结点的内存空间。
5. 返回链表的头指针。
完整代码如下:
```
typedef struct node {
int data;
struct node *next;
} Node;
Node* deletePreNode(Node *s) {
if (s == NULL || s->next == NULL) {
return NULL;
}
Node *p = s->next;
Node *pre = s;
while (p->next != s) {
pre = p;
p = p->next;
}
if (s == pre->next) {
pre->next = s->next;
free(s);
} else {
Node *temp = pre->next;
pre->next = temp->next;
free(temp);
}
return s->next;
}
```