对于不带头结点的单链表L,设计一个递归算法删除第一个值为x的结点c++
时间: 2023-11-27 11:53:06 浏览: 86
下面是递归算法的C++代码实现:
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
void deleteNode(ListNode* &head, int x) {
if (!head) return; // 空链表,直接返回
if (head->val == x) { // 如果头结点就是要删除的结点
ListNode* temp = head;
head = head->next;
delete temp;
return;
}
deleteNode(head->next, x); // 递归删除下一个结点
return;
}
```
需要注意的是,由于需要修改链表的头结点,所以需要传入指向头结点的指针的引用。同时,为了方便递归操作,我们采用了尾递归的形式,每次递归操作都是删除下一个结点,直到找到需要删除的结点或者到达链表结尾。
相关问题
对于不带头结点的单链表L,设计一个递归算法删除第一个值为x的结点
递归算法的思路是将链表分为两个部分,第一个部分是以第一个结点为头结点的子链表,第二个部分就是剩下的结点组成的子链表。然后对第二个子链表进行递归操作,再把第一个子链表和结果拼接起来即可。
具体实现步骤如下:
1. 若链表L为空,则无法删除,返回NULL。
2. 若链表L的第一个结点的值等于x,则将第一个结点删除,并返回第二个结点。
3. 否则,对链表L中除第一个结点外的剩余结点进行递归操作,得到新的链表。
4. 将链表L的第一个结点和新链表拼接起来,返回新链表。
C++代码如下:
```c++
struct ListNode{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL){}
};
ListNode* deleteNode(ListNode* L, int x){
if(!L) return NULL; //链表为空
if(L->val == x){ //第一个结点就是要删除的结点
ListNode* tmp = L;
L = L->next;
delete tmp;
return L;
}
L->next = deleteNode(L->next, x); //递归操作
return L;
}
```
对于不带头结点的单链表L,设计一个递归算法删除第一个值为x的结点。
递归算法的基本思想是将问题转化为更小的问题,直到问题规模足够小,可以直接求解。在这个问题中,我们可以将删除第一个值为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);
}
```
需要注意的是,由于我们需要修改指针指向,因此在递归调用时需要使用引用或指针传递指针。
阅读全文