编写递归算法实现,删除以L为首节点指针的单链表中值为x的所有节点
时间: 2024-10-24 15:14:11 浏览: 26
递归链表中值最大的节点
4星 · 用户满意度95%
在C++中,要编写一个递归算法来删除单链表中所有值为`x`的节点,我们可以使用一个辅助函数,该函数接受当前节点`curr`以及前驱节点`prev`作为参数。递归的基本思想是先处理当前节点,然后递归地处理剩余的链表。
这里是一个示例代码:
```cpp
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`的节点。注意,我们使用了引用传递,使得函数可以在递归过程中修改链表结构。
阅读全文