删除带头结点单链表head的第一个值为x的结点
时间: 2024-03-25 15:15:02 浏览: 37
要删除带头结点单链表head的第一个值为x的结点,可以按照以下步骤进行:
1. 定义两个指针p和pre,分别指向头结点和头结点的前驱结点(即空结点)。
2. 从头结点开始,依次遍历单链表,直到找到第一个值为x的结点。
3. 如果找到了值为x的结点,则让pre的next指向该结点的next,然后释放该结点的空间。
4. 如果遍历到链表末尾仍未找到值为x的结点,则输出提示信息。
下面是具体的代码实现:
```
void deleteNode(Node* head, int x) {
Node* p = head->next;
Node* pre = head;
while (p != NULL) {
if (p->data == x) {
pre->next = p->next;
free(p);
return;
}
pre = p;
p = p->next;
}
printf("未找到值为%d的结点\n", x);
}
```
相关问题
编写函数删除不带头结点单链表head中的第一个值为x的结点,并构造测试用例进行测试
可以使用以下代码来删除不带头结点单链表head中的第一个值为x的结点:
```
void deleteNode(ListNode* head, int x) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr && curr->val != x) {
prev = curr;
curr = curr->next;
}
if (curr != nullptr) {
if (prev != nullptr) {
prev->next = curr->next;
} else {
head = curr->next;
}
delete curr;
}
}
```
测试用例可以包括以下情况:
- 删除的结点是头结点
- 删除的结点是尾结点
- 删除的结点是中间结点
- 删除的结点不存在
例如:
```
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
deleteNode(head, 2); // 删除中间结点
deleteNode(head, 1); // 删除头结点
deleteNode(head, 4); // 删除尾结点
deleteNode(head, 5); // 删除不存在的结点
```
注意:在实际使用中,需要根据具体情况来确定是否需要传入头结点的指针。如果需要删除头结点,需要更新头结点的指针。
递归删除不带头结点的单链表L中所有值为x的结点
递归删除不带头结点的单链表L中所有值为x的结点,可以按照以下步骤进行:
1. 如果链表为空,则直接返回;
2. 否则,对于当前链表的第一个结点,如果其值为x,则将其删除,并递归删除剩余部分中所有值为x的结点;
3. 否则,递归删除剩余部分中所有值为x的结点。
具体的删除操作可以使用指针进行实现,代码如下:
```c++
void deleteNode(ListNode*& node, int x) {
if (node == nullptr) {
return;
}
if (node->val == x) {
ListNode* next = node->next;
delete node;
node = next;
deleteNode(node, x);
} else {
deleteNode(node->next, x);
}
}
```
其中,ListNode是单链表的结点类型,其定义如下:
```c++
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
```
在调用上述函数时,需要传入链表的头结点的指针,例如:
```c++
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(2);
deleteNode(head, 2);
```
执行完上述代码后,链表中所有值为2的结点都会被删除。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)