实现一个基本操作，查找并返回链表中某个已知结点p的前驱结点

可以使用双指针法，定义两个指针pre和cur，初始时pre指向头结点，cur指向第一个结点。然后遍历链表，如果cur指向的结点是p，则返回pre指向的结点，否则pre指向cur，cur指向下一个结点，继续遍历。如果遍历完整个链表都没有找到p，则返回空。

相关问题

假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点

### 回答1：
算法如下：

1. 如果链表长度小于等于1，无法删除前驱结点，直接返回。

2. 遍历链表，找到指针s所指结点的前驱结点p和后继结点q。

3. 如果p是链表的最后一个结点，则将q作为新的尾结点，并将其next指针指向链表的头结点。

4. 否则，将p的next指针指向q，即删除p结点。

代码实现：

void deletePreNode(Node* s) {
if (s == NULL || s->next == NULL) {
return; // 链表长度小于等于1，无法删除前驱结点
}
Node* p = s;
Node* q = s->next;
while (q->next != s) {
p = p->next;
q = q->next;
}
if (p == q) {
// s指向头结点，p指向尾结点
p->next = s->next;
} else {
// 删除p结点
p->next = q;
}
}

### 回答2：
题目要求我们在一个没有头指针和头结点的循环链表中删除指针s所指结点的前驱结点，我们可以依次遍历链表，找到s所指结点，然后再找到其前驱结点，最后删除前驱结点。

首先，我们需要遍历链表，找到s所指结点和其前驱结点。由于链表为循环链表，我们需要设置两个指针p和q，使其分别指向链表中的相邻两个结点，并顺序遍历链表。当p指向s所指结点时，q指向的就是其前驱结点。具体实现代码如下：

Node *p = head->next;
Node *q = head;
while(p != s) {
q = p;
p = p->next;
}

找到前驱结点后，我们需要进行删除操作。由于链表为循环链表，因此删除操作需要特殊处理第一个结点的情况。如果要删除第一个结点的前驱结点，那么需要将最后一个结点的next指针指向第二个结点，即将head->next指向q->next。具体实现代码如下：

if(q == head) {
head->next = q->next;
} else {
q->next = q->next->next;
}
delete q->next;

最后，需要注意一些特殊情况的处理。如果链表长度小于等于1，或者s所指结点为链表的第一个结点，那么该算法无法进行操作；如果s所指结点为链表的最后一个结点，则其前驱结点为链表的最后一个结点，需要对其进行特殊处理。具体实现代码如下：

if(head == NULL || head->next == NULL || s == head->next) {
return;
}
if(s->next == head->next) {
q = s;
while(q->next != head->next) {
q = q->next;
}
}

最终实现的删除指针s所指结点的前驱结点的算法如下：

void deletePre(Node *s) {
Node *p = head->next;
Node *q = head;
if(head == NULL || head->next == NULL || s == head->next) {
return;
}
if(s->next == head->next) {
q = s;
while(q->next != head->next) {
q = q->next;
}
}
while(p != s) {
q = p;
p = p->next;
}
if(q == head) {
head->next = q->next;
} else {
q->next = q->next->next;
}
delete q->next;
}

### 回答3：
这道题需要我们先理解循环链表的概念，循环链表是指尾结点指向表头结点的链表，即形成了一个环。

我们需要删除的是指向s的前驱结点，在循环链表中，前驱结点是指在s之前的结点。但是需要注意的是，在循环链表中，尾结点的前驱结点是表头结点。因此，我们需先找到s的前驱结点p：

1. 从链表头开始遍历链表，直到找到一个结点x，使得x->next等于s。
2. 如果找到了这样的结点x，则其前驱结点为p，即p = x。
3. 如果遍历到尾结点仍未找到x，则表明s不存在于链表中，无法删除其前驱结点。

找到p后，我们可以进行删除操作。由于链表为循环链表，删除p的方法需要注意：

1. 如果p是头结点，直接将头指针指向s即可。
2. 如果p不是头结点，则需要找到其前驱结点q，并使其指向s，即q->next = s。
3. 如果p是尾结点，则需要找到其前驱结点q，并使其指向表头结点，即q->next = s->next。同时，需要更新头结点指针，使其指向s->next。

综上所述，我们可以得到如下算法：

Algorithm delete_predecessor(s: pointer to node)
p = head // 从头结点开始遍历链表
while p->next != s do
p = p->next
if p == head then
p = tail // 如果在头结点处没找到s，从尾结点开始查找
end while
if p == tail then
q = head
while q->next != tail do // 找到尾结点的前驱结点
q = q->next
end while
q->next = s->next // 使其指向表头结点
head = s->next // 更新头指针
else
if p == head then // 如果p是头结点
head = s
else // p不是头结点
q = head
while q->next != p do // 找到p的前驱结点
q = q->next
end while
q->next = s // 使其指向s
end if
end if
end Algorithm

注意，以上算法需要考虑循环链表的特殊性质，对于普通链表无法使用。此外，算法仅删除指向s的前驱结点，对于s本身不会进行删除。

假设某个单向循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表中某个结点的指针，试编写算法在链表中删除指针s所指结点的前驱结点。

由于是单向循环链表，无法直接访问前驱结点。因此，需要遍历整个链表，找到s的前驱结点，并将其删除。

具体实现步骤如下：

1. 定义一个指针p，初始指向s所指向的结点。

2. 从p开始遍历整个链表，直到找到p的前驱结点。

3. 在遍历过程中，定义一个指针q，始终指向p的前一个结点。

4. 如果p遍历到链表的末尾，即p指向的结点为链表的尾结点，则q指向的结点为链表的头结点。

5. 将q所指向的结点从链表中删除即可。

具体实现代码如下：

void deletePreNode(Node* s) {
    Node* p = s;
    Node* q = NULL;
    while (p->next != s) {
        q = p;
        p = p->next;
    }
    if (q == NULL) { // s的前驱结点为链表的尾结点，q指向头结点
        q = p;
        while (q->next != p) {
            q = q->next;
        }
    }
    q->next = p->next;
    free(p);
}

注意，此算法的时间复杂度为O(n)，其中n为链表的长度。因此，如果链表很长，效率可能较低，建议考虑其他实现方式。