编写递归算法实现删除以L为首节点指针的单链表中值为x的所有节点

递归算法删除单链表中值为 `x` 的所有节点通常涉及两个步骤：首先判断当前节点是否需要删除，然后处理剩余部分。如果当前节点的值等于 `x`，则删除它，并让下一个节点指向当前节点的下一个；如果当前节点不是目标值，则将下一个节点传递给递归函数。

以下是 Python 中的递归示例：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

def delete_nodes(head, x):
    # Base case: 如果链表为空或者头节点就是要删除的节点
    if not head or head.data == x:
        return None

    # 递归处理剩余部分，让当前节点的下一个节点继续递归
    head.next = delete_nodes(head.next, x)
    
    return head

这个函数会遍历整个链表，直到找到第一个不是 `x` 的节点，然后继续对剩下的链表进行同样的操作。最后返回新链表的头节点，原来的 `head` 节点及其后续所有值为 `x` 的节点已被删除。

相关问题

编写递归算法实现，删除以L为首节点指针的单链表中值为x的所有节点

在C++中，要编写一个递归算法来删除单链表中所有值为`x`的节点，我们可以使用一个辅助函数，该函数接受当前节点`curr`以及前驱节点`prev`作为参数。递归的基本思想是先处理当前节点，然后递归地处理剩余的链表。

这里是一个示例代码：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

void deleteNodes(ListNode *&head, int x, ListNode *&prev) {
    // 如果链表为空或当前节点就是要删除的值
    if (!head || head->val == x) {
        // 删除头节点（如果必要）
        if (head && head->val == x) {
            prev = head;
            head = head->next;
        }
        return;
    }

    // 不是我们要删除的值，继续处理下一个节点
    deleteNodes(head->next, x, head); // 递归调用，prev更新为current

    // 更新prev和head，以便于下一轮迭代
    prev = head;
}

// 主函数，用于删除整个链表中的特定值
void removeDuplicates(ListNode *&head, int x) {
    deleteNodes(head, x, nullptr); // 使用nullptr初始化prev，表示头节点就是头节点
}

这个函数的工作原理是，从头开始遍历链表，如果遇到值为`x`的节点，就递归地跳过它直到找到非`x`的节点，然后将前驱节点指向这个非`x`的节点。注意，我们使用了引用传递，使得函数可以在递归过程中修改链表结构。

算法实现，删除以L为首节点指针的单链表中值为x的所有节点 C++

在C++中，如果你想要删除单链表中所有值为`x`的节点，从给定的首节点`L`开始，你可以采用迭代或者递归的方式来实现。这里我将展示一种迭代的方法：

#include <iostream>

// 定义链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 删除链表中值为x的节点
ListNode* removeElements(ListNode* L, int x) {
    if (L == nullptr || L->val != x) {
        return L;
    }
    
    // 使用迭代，创建新头结点并更新指向下一个不是x的节点
    ListNode* dummy = new ListNode(0);  // 创建虚拟头结点
    dummy->next = L;
    ListNode* current = dummy;

    while (current->next != nullptr && current->next->val == x) {
        current->next = current->next->next;
    }

    return dummy->next;  // 返回新链表的第一个非x节点
}

int main() {
    // 示例链表：1 -> 2 -> 3 -> 4 -> 2 -> 5
    ListNode* L = new ListNode(1);
    L->next = new ListNode(2);
    L->next->next = new ListNode(3);
    L->next->next->next = new ListNode(4);
    L->next->next->next->next = new ListNode(2);
    L->next->next->next->next->next = new ListNode(5);

    // 删除值为2的节点
    ListNode* result = removeElements(L, 2);
    while (result != nullptr) {
        std::cout << result->val << " ";
        result = result->next;
    }
    std::cout << "\n";

    delete L;  // 别忘了释放内存
    return 0;
}

在这个代码中，我们首先检查头节点是否就是我们要删除的节点，如果不是，则直接返回头节点。然后，通过迭代遍历链表，遇到值为`x`的节点就跳过它，直到找到第一个不是`x`的节点。最后返回这个新头部。