数据结构 从未排序的链表中删除重复项python
时间: 2024-10-14 20:03:34 浏览: 3
在Python中,从一个未排序的链表中删除重复项可以使用哈希集合(set)配合迭代的方式来完成。这里是一个简单的示例:
```python
class Node:
def __init__(self, val=None):
self.val = val
self.next = None
def remove_duplicates(head):
if not head or not head.next:
return head
current = head
seen = set()
while current:
if current.val in seen:
# 如果当前节点值已经在seen中,则跳过这个节点
current = current.next
else:
seen.add(current.val)
current = current.next
return head
```
这个函数会遍历链表,如果遇到的值已经在`seen`集合中(即重复),就直接跳过;否则,将值添加到集合中,并继续前进。最后返回处理后的链表头节点。
相关问题
CShap 已排序的链表中删除重复项 源代码
以下是C#中已排序的链表中删除重复项的源代码:
```
public ListNode DeleteDuplicates(ListNode head)
{
if (head == null || head.next == null)
return head;
ListNode current = head;
while (current != null && current.next != null)
{
if (current.val == current.next.val)
{
current.next = current.next.next;
}
else
{
current = current.next;
}
}
return head;
}
```
在这个方法中,我们首先检查链表是否为空或只有一个元素。如果是这样,我们返回原始链表。然后,我们定义一个当前节点变量,并将其设置为链表的头部。
我们使用 while 循环遍历链表,如果当前节点的值与下一个节点的值相同,则我们将当前节点的下一个节点指向下一个节点的下一个节点。否则,我们将当前节点移动到下一个节点。
最后,我们返回链表的头部。
c++删除排序链表中的重复元素
在C++中,删除排序链表中的重复元素通常需要遍历链表,同时维护两个指针,一个用于当前节点,另一个用于检查是否有重复的元素。以下是基本的步骤:
1. 定义一个头指针`prev`,初始值为`nullptr`,用于记录前一个节点;定义一个`current`指针指向链表的第一个节点。
2. 遍历链表,对于每个节点`current`:
a. 如果`current->val`等于`prev->val`并且`prev`不为`nullptr`,说明找到了重复元素,将`prev`节点的下一个节点设置为`current`,然后移动`prev`到`current`,继续检查下一个节点。
b. 否则,如果`prev`等于`nullptr`或者`current->val`大于`prev->val`,说明当前节点是一个新的不重复元素,将`prev`更新为`current`。
3. 遍历结束后,链表中的重复元素已经被删除,`current`就是新链表的最后一个节点。
```cpp
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;
ListNode* prev = nullptr, *current = head;
while (current != nullptr) {
if (current->val == prev->val && prev != nullptr) {
prev->next = current->next;
} else {
prev = current;
}
current = current->next;
}
return head;
}
```