对于不带头结点的单链表L,设计一个递归算法删除第一个值为x的结点。
时间: 2023-11-27 08:49:52 浏览: 95
单链表的递归算法设计-递归算法设计技术ppt
递归算法的基本思想是将问题转化为更小的问题,直到问题规模足够小,可以直接求解。在这个问题中,我们可以将删除第一个值为x的结点的问题转化为删除除头结点外的第一个值为x的结点的问题。
具体实现如下:
1. 如果链表为空,直接返回。
2. 如果头结点的值等于x,删除头结点并返回。
3. 如果头结点的值不等于x,递归调用删除除头结点外的第一个值为x的结点。
代码实现如下:
```c++
void deleteNode(Node* p, int x) {
if (p == nullptr) return;
if (p->val == x) {
Node* q = p;
p = p->next;
delete q;
return;
}
deleteNode(p->next, x);
}
```
需要注意的是,由于我们需要修改指针指向,因此在递归调用时需要使用引用或指针传递指针。
阅读全文