有表头的链表怎么删除链表里的重复数据
时间: 2023-07-12 20:54:25 浏览: 45
对于有表头的链表,可以采用哈希表的思想来删除链表里的重复数据。具体步骤如下:
1. 定义一个哈希表,用于记录链表中已经出现过的元素。
2. 从链表的头节点开始遍历链表,对于每个遍历到的节点,判断它的值是否在哈希表中出现过。
3. 如果该节点的值已经出现过,则将该节点从链表中删除。
4. 如果该节点的值没有出现过,则将该节点的值添加到哈希表中。
5. 继续遍历链表,直到链表结束。
需要注意的是,删除节点时需要注意链表的头节点,因为头节点不需要判断是否重复。另外,删除节点时需要保留当前节点的前一个节点,以便将当前节点从链表中删除。
相关问题
有表头链表和无表头链表删除相同数据的方式一致吗?
有表头链表和无表头链表删除相同数据的方式基本一致,只是在删除头节点时需要特殊处理。
对于有表头链表,删除重复数据的方法与无表头链表类似,只需要从头节点开始遍历链表,对于每个节点,判断其值是否出现过,如果出现过,则将该节点从链表中删除,否则将该节点的值添加到哈希表中。
对于无表头链表,也是从头节点开始遍历链表,不同之处在于,删除头节点时需要将头节点指向下一个节点,而不是将头节点从链表中删除。
下面是无表头链表删除重复数据的示例代码,与有表头链表的代码类似:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_duplicates(head: ListNode) -> ListNode:
# 定义哈希表和指针变量
hash_set = set()
cur = head
pre = None
# 遍历链表
while cur:
# 如果该节点的值已经出现过,则将该节点从链表中删除
if cur.val in hash_set:
pre.next = cur.next
cur = cur.next
# 如果该节点的值没有出现过,则将该节点的值添加到哈希表中
else:
hash_set.add(cur.val)
pre = cur
cur = cur.next
return head
```
以上代码中,使用哈希表记录链表中已经出现过的元素,指针变量 `pre` 用于记录当前节点的前一个节点,以便将当前节点从链表中删除。当当前节点的值已经出现过时,将当前节点从链表中删除,并将指针 `cur` 指向下一个节点;否则将当前节点的值添加到哈希表中,并将指针 `pre` 和 `cur` 都指向下一个节点。最后返回头节点即可。
有表头的链表怎么删除链表里的重复数据,写出代码
以下是用哈希表实现删除重复节点的示例代码,其中假设链表的节点类型为 `ListNode`,包含一个整型的数据成员 `val` 和一个指向下一个节点的指针 `next`:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def delete_duplicates(head: ListNode) -> ListNode:
# 定义哈希表和指针变量
hash_set = set()
cur = head
pre = None
# 遍历链表
while cur:
# 如果该节点的值已经出现过,则将该节点从链表中删除
if cur.val in hash_set:
pre.next = cur.next
# 如果该节点的值没有出现过,则将该节点的值添加到哈希表中
else:
hash_set.add(cur.val)
pre = cur
# 继续遍历链表
cur = cur.next
return head
```
以上代码中,使用哈希表记录链表中已经出现过的元素,指针变量 `pre` 用于记录当前节点的前一个节点,以便将当前节点从链表中删除。最后返回头节点即可。