链表类删除重复元素
时间: 2023-08-04 14:14:58 浏览: 51
链表类删除重复元素可以通过遍历链表,使用哈希表存储已经出现过的元素,如果遍历到的元素已经在哈希表中出现过,就删除该元素。具体实现可以参考以下代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def deleteDuplicates(head: ListNode) -> ListNode:
if not head:
return None
hash_map = {}
pre = None
cur = head
while cur:
if cur.val not in hash_map:
hash_map[cur.val] = True
pre = cur
else:
pre.next = cur.next
cur = cur.next
return head
```
这段代码中,我们使用了一个哈希表 `hash_map` 存储已经出现过的元素。遍历链表时,如果当前元素不在哈希表中,就将其加入哈希表,并将 `pre` 指向当前元素;否则,就将 `pre.next` 指向当前元素的下一个节点,从而删除当前节点。最后返回原链表的头节点 `head`。
相关问题
利用puthon删除排列链表中的重复元素
可以利用 Python 的 set() 函数来实现删除排列链表中的重复元素。具体步骤如下:
1. 定义一个链表节点类 ListNode,包括节点值 val 和下一个节点 next。
2. 定义一个链表类 LinkedList,包括链表头节点 head 和链表长度 size。
3. 定义一个 deleteDuplicates() 方法,遍历链表并将节点值放入 set 中。如果节点值已经在 set 中出现过,则删除该节点。
4. 最后返回删除重复节点后的链表头节点。
下面是代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class LinkedList:
def __init__(self):
self.head = None
self.size = 0
def deleteDuplicates(self):
if not self.head:
return
node_set = set()
node_set.add(self.head.val)
prev = self.head
while prev.next:
curr = prev.next
if curr.val in node_set:
prev.next = curr.next
else:
node_set.add(curr.val)
prev = curr
def insert(self, val):
node = ListNode(val)
if not self.head:
self.head = node
else:
curr = self.head
while curr.next:
curr = curr.next
curr.next = node
self.size += 1
def __str__(self):
if not self.head:
return "Empty LinkedList"
curr = self.head
lst = []
while curr:
lst.append(curr.val)
curr = curr.next
return "->".join(map(str, lst))
# Example usage
ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.insert(2)
ll.insert(4)
ll.insert(1)
print(ll) # 1->2->3->2->4->1
ll.deleteDuplicates()
print(ll) # 1->2->3->4
```
在上面的代码中,我们创建了一个简单的链表并插入了一些元素。然后我们调用 `deleteDuplicates()` 方法来删除重复元素,并打印链表以验证结果。
用c++写一个能删除链表类重复元素的函数
好的,下面是用 C++ 实现删除链表类重复元素的函数:
```c++
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* deleteDuplicates(ListNode* head) {
if (!head) {
return NULL;
}
unordered_map<int, bool> hash_map;
ListNode* pre = NULL;
ListNode* cur = head;
while (cur) {
if (hash_map.find(cur->val) == hash_map.end()) {
hash_map[cur->val] = true;
pre = cur;
} else {
pre->next = cur->next;
delete cur;
}
cur = pre->next;
}
return head;
}
```
这里使用了 STL 中的 `unordered_map` 来实现哈希表,与 Python 中的字典类似。遍历链表时,如果当前元素不在哈希表中,就将其加入哈希表,并将 `pre` 指向当前元素;否则,就将 `pre->next` 指向当前元素的下一个节点,并删除当前节点。最后返回原链表的头节点 `head`。