已知一无头结点的单链表，头指针为HEAD，写一算法，删除表中数据值为f的所有元素

以下是删除单链表中值为f的所有元素的算法实现：

ListNode* prev = NULL; // 前驱结点
ListNode* curr = HEAD; // 当前结点

while (curr != NULL) {
    if (curr->val == f) {
        if (prev == NULL) { // 删除头结点
            HEAD = curr->next;
        } else {
            prev->next = curr->next;
        }
        ListNode* temp = curr;
        curr = curr->next;
        delete temp;
    } else {
        prev = curr;
        curr = curr->next;
    }
}

算法思路：

使用两个指针变量：prev 和 curr，分别指向当前结点的前驱结点和当前结点。从头结点开始遍历单链表，如果当前结点的值等于 f，则删除当前结点。删除当前结点时，需要将前驱结点的 next 指针指向当前结点的下一个结点，然后释放当前结点的内存空间。如果当前结点的值不等于 f，则更新 prev 和 curr 指针的值，继续向后遍历单链表。当 curr 指向空结点时，遍历结束。

相关问题

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

如果链表的长度小于等于1或者s为NULL，则无法删除前驱结点，直接返回。

否则，先找到s所指向的结点的前驱结点pre和后继结点next。如果s指向的是第一个结点，则pre为链表的最后一个结点；如果s指向的是最后一个结点，则next为链表的第一个结点。

然后，将pre的next指针指向next，并释放原来的s所指向的结点。

最后，如果s指向的是第一个结点，则将链表的头指针指向next；如果s指向的是最后一个结点，则将链表的尾指针指向pre。

具体实现如下：

void deletePreNode(node* s) {
    if (s == NULL || s->next == s) { // 链表长度小于等于1或者s为NULL，无法删除前驱结点
        return;
    }
    node* p = s->next; // p指向s的后继结点
    node* q = s; // q指向s
    while (q->next != s) { // 找到s的前驱结点
        q = q->next;
    }
    node* pre = q; // pre指向s的前驱结点
    node* next = p; // next指向s的后继结点
    while (next->next != s) { // 找到s的后继结点
        next = next->next;
    }
    pre->next = next; // 删除pre的后继结点，将pre的next指针指向next
    free(s); // 释放s所指向的结点
    if (s == pre->next) { // 如果s指向的是第一个结点
        head = next; // 将链表的头指针指向next
    }
    if (s == next) { // 如果s指向的是最后一个结点
        tail = pre; // 将链表的尾指针指向pre
    }
}

已知带头结点的单链表L，请写一算法，删除所有数据元素值为x的结点。要求：定义 单链表的存储结构并分析算法的时间复杂度。

首先，我们需要定义单链表的节点结构，通常它包含两个部分：一个数据域data用于存储元素值，另一个指针域next连接到下一个节点：

struct ListNode {
    int data;
    ListNode* next;
    ListNode(int x) : data(x), next(nullptr) {}
};

接下来，我们可以编写一个函数来删除所有值为x的节点：

void removeNodes(ListNode* &head, int x) {
    if (head == nullptr || head->data != x) { // 如果头节点不存在或者头节点不是目标值，直接返回
        return;
    }

    ListNode* prev = nullptr;
    ListNode* curr = head;

    while (curr != nullptr && curr->data == x) { // 遍历链表，遇到值为x的节点
        ListNode* nextNode = curr->next;
        if (prev == nullptr) { // 如果是头节点，更新头节点
            head = nextNode;
        } else {
            prev->next = nextNode; // 删除当前节点
        }
        delete curr; // 释放内存
        curr = nextNode; // 移动到下一个节点
        prev = curr; // 更新前驱节点
    }
}

该算法的时间复杂度是O(n)，其中n是链表的长度。因为我们只遍历一次链表，并在每个节点上进行常数时间的操作（查找、删除和内存释放）。如果x不在链表中，此操作不会改变链表的实际长度。