首页C++：已知单链表 L 中的结点是按值非递减有序排列的，试编写一算法将链表 L 中值为 X 的结点删除，使得 L 仍然有序。

C++：已知单链表 L 中的结点是按值非递减有序排列的，试编写一算法将链表 L 中值为 X 的结点删除，使得 L 仍然有序。

时间: 2024-10-24 15:08:38 浏览: 65

在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`的节点，就直接跳过它并删除，同时保证链表始终保持有序。

阅读全文