设单链表以非递减有序排列,设计算法实现在单链表中删除值相同的多余结点。
时间: 2024-10-19 19:10:24 浏览: 34
链表结点的C++描述-单链表的实现-简单操作
要在单链表中删除值相同的多余节点,我们需要遍历整个链表并检查每个节点的值是否与其前一个节点相同。如果发现相同,我们可以跳过当前节点,直到找到值不同的节点或链表尾部。这里是一个简单的C++算法实现:
```cpp
#include <iostream>
struct Node {
int value;
Node* next;
};
// 创建新节点
Node* createNode(int val) {
Node* newNode = new Node();
newNode->value = val;
newNode->next = nullptr;
return newNode;
}
// 删除重复节点(不包括头节点)
void removeDuplicates(Node*& head) {
if (head == nullptr || head->next == nullptr) {
return; // 如果链表为空或只有一个节点,无需处理
}
Node* current = head;
Node* previous = nullptr;
while (current != nullptr) {
Node* nextTemp = current->next;
if (previous && current->value == previous->value) {
delete current;
current = nextTemp;
continue;
}
previous = current;
current = nextTemp;
}
}
// 打印链表帮助测试
void printList(Node* node) {
while (node != nullptr) {
std::cout << node->value << " -> ";
node = node->next;
}
std::cout << "nullptr" << std::endl;
}
int main() {
// 示例链表:1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 4
Node* head = createNode(1);
head->next = createNode(2);
head->next->next = createNode(2);
head->next->next->next = createNode(3);
head->next->next->next->next = createNode(3);
head->next->next->next->next->next = createNode(3);
head->next->next->next->next->next->next = createNode(4);
std::cout << "Original list before removing duplicates:\n";
printList(head);
removeDuplicates(head);
std::cout << "\nList after removing duplicates:\n";
printList(head);
return 0;
}
```
这个算法首先创建一个`removeDuplicates`函数,接受链表的头指针作为参数。我们使用两个指针`current`和`previous`,分别指向当前节点和它的前一个节点。如果当前节点的值等于前一个节点的值,就删除当前节点。否则,移动`previous`和`current`到下一个节点。
在`main`函数中,我们创建了一个示例链表并调用`removeDuplicates`来演示其效果。你可以根据自己的需求调整链表的构造。
阅读全文