C++:已知单链表 L 中的结点是按值非递减有序排列的,试编写一算法将链表 L 中值为 X 的结点 删除,使得 L 仍然有序。
时间: 2024-10-24 11:08:38 浏览: 32
在C++中,如果给定的单链表`L`是一个非递减有序列表,并且需要删除所有值为`X`的节点,可以采用迭代或递归的方式来实现这个操作。这里我会提供一个迭代的解决方案:
```cpp
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
void removeElement(ListNode* &head, int X) {
ListNode* dummy = new ListNode(0); // 创建虚拟头节点
dummy->next = head; // 将虚拟头链接到实际头
ListNode* prev = dummy; // 初始化前驱指针
ListNode* curr = head; // 初始化当前指针
while (curr != nullptr) {
if (curr->val == X) { // 如果当前节点值等于X
prev->next = curr->next; // 删除当前节点
delete curr; // 并释放内存
} else {
prev = curr; // 否则,更新前驱指针
}
curr = curr->next; // 移动到下一个节点
}
// 更新实际头节点为虚拟头的下一个节点
head = dummy->next;
delete dummy; // 删除虚拟头节点
}
```
这个函数首先创建了一个虚拟头节点,然后遍历整个链表。如果遇到值为`X`的节点,就直接跳过它并删除,同时保证链表始终保持有序。
阅读全文