题目

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

image.png

思路

第一种做法，用hash-set存储出现过的值。

枚举待移除节点的前驱节点。（因为直接枚举待移除节点，本自杀是将它的前驱节点连向后继节点。进一步，由于是链表结构，无法直接范围一个节点的前驱节点。因此考虑枚举待移除节点的前驱节点。）

使用临时缓冲区，其实就是时间换空间的做法，使用两层循环。不推荐！

代码

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     def removeDuplicateNodes(self, head: ListNode) -> ListNode:
  9.         # hash表
  10.         if not head:
  11.             return head
  12.         node = head
  13.         hash_set = {node.val}
  14.         while node.next:
  15.             cur = node.next
  16.             if cur.val not in hash_set:
  17.                 hash_set.add(cur.val)
  18.                 node = node.next
  19.             else:
  20.                 node.next = node.next.next
  22.         return head