将单链表中重复元素删除
时间: 2024-05-14 20:13:44 浏览: 7
可以通过遍历单链表,使用一个哈希表记录每个元素出现的次数,如果出现次数大于1,则删除该节点。具体实现如下:
1. 定义一个哈希表,记录每个元素出现的次数。
2. 定义两个指针,一个指向当前节点,一个指向前一个节点。
3. 遍历单链表,当遇到重复元素时,删除当前节点。
4. 更新当前节点和前一个节点指针。
以下是示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_duplicates(head: ListNode) -> ListNode:
if head is None:
return None
# 定义哈希表和指针
hash_table = {}
curr = head
prev = None
while curr:
# 如果当前元素出现次数大于1,删除该节点
if curr.val in hash_table and hash_table[curr.val] > 0:
if prev is None:
head = curr.next
else:
prev.next = curr.next
curr = curr.next
else:
# 更新哈希表和指针
hash_table[curr.val] = 1
prev = curr
curr = curr.next
return head
```
时间复杂度为 $O(n)$,空间复杂度为 $O(n)$。