有一个非空整数单链表L,设计一个算法删除值重复的节点,多个值相同的节点仅保留第一个。 输入 8 1 4 1 2 2 1 3 4 输出 1 4 2 3C++实现
时间: 2024-09-29 09:01:20 浏览: 17
这是一个常见的链表操作问题,可以通过遍历链表并利用哈希集合来解决。以下是C++的一个简单实现:
```cpp
#include <unordered_set>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
unordered_set<int> seen;
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
if (seen.find(curr->val) == seen.end()) {
seen.insert(curr->val);
prev = curr;
} else {
prev->next = curr->next;
}
curr = prev->next;
}
return head;
}
```
这个函数的工作原理是遍历链表,遇到新值就将其添加到哈希集合`seen`中,并将指针`prev`移动到当前节点。如果遇到重复值,则跳过当前节点,使得`prev->next`指向下一个节点。最后返回头节点即可。