有表头链表和无表头链表删除相同数据的方式一致吗?
时间: 2023-07-11 11:51:02 浏览: 81
有表头链表和无表头链表删除相同数据的方式基本一致,只是在删除头节点时需要特殊处理。
对于有表头链表,删除重复数据的方法与无表头链表类似,只需要从头节点开始遍历链表,对于每个节点,判断其值是否出现过,如果出现过,则将该节点从链表中删除,否则将该节点的值添加到哈希表中。
对于无表头链表,也是从头节点开始遍历链表,不同之处在于,删除头节点时需要将头节点指向下一个节点,而不是将头节点从链表中删除。
下面是无表头链表删除重复数据的示例代码,与有表头链表的代码类似:
```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` 都指向下一个节点。最后返回头节点即可。
阅读全文