面试题 02.01. 移除重复节点

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

示例1:

输入：[1, 2, 3, 3, 2, 1]
输出：[1, 2, 3]

示例2:

输入：[1, 1, 1, 1, 2]
输出：[1, 2]
提示：

链表长度在[0, 20000]范围内。
链表元素在[0, 20000]范围内。

进阶：

• 如果不得使用临时缓冲区，该怎么解决？

Python 解答：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        aset = set()
        p = ListNode(-1)
        pre = p
        while head:
            if head.val not in aset:
                aset.add(head.val)
                pre.next = head
                pre = head
                head = head.next
            else:
                head = head.next
        pre.next = None
        return p.next

2.时间换空间

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        pre = head
        q = head
        while q:
            cur = q.next
            while cur:
                if cur.val != q.val:
                    cur = cur.next
                    pre = pre.next
                else:
                    pre.next = cur.next
                    cur = cur.next
            q = q.next
            pre = q
        return head