难度:简单

知识点:链表

地址:https://leetcode-cn.com/problems/remove-duplicate-node-lcci/

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

示例1:

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

示例2:

输入:[1, 1, 1, 1, 2]
输出:[1, 2]

提示:

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

进阶:

如果不得使用临时缓冲区,该怎么解决?

思路1

  • 使用哈希表来做重复节点的过滤,使用新链表来装数据
  • 遍历原链表,如果节点不在哈希表中,则加入到新链表中。如果节点已经存在,则跳过
  • 最后返回新链表
In [12]:
from utils import ListNode
from utils import array2listnode
from utils import listnode2array

class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        '''
        执行用时: 96 ms , 在所有 Python3 提交中击败了 44.85% 的用户
        内存消耗: 23 MB , 在所有 Python3 提交中击败了 100.00% 的用户
        '''
        l3 = ListNode(0)
        l4 = l3
        stack = set()
        while head:
            val = head.val
            if val not in stack:
                stack.add(val)
                l4.next = ListNode(val)
                l4 = l4.next
            head = head.next
        return l3.next

s = Solution()
assert listnode2array(s.removeDuplicateNodes(array2listnode([1, 2, 3, 3, 2, 1]))) == [1, 2, 3]
assert listnode2array(s.removeDuplicateNodes(array2listnode([1, 1, 1, 1, 2]))) == [1, 2]

思路2

  • 整体思路与上面相同,只是不用新链表,而是在原链表中做删除
  • 如果 head.next 是否出现在哈希表中,如果出现过,则 head.next = head.next.next 跳过
  • 最后返回当前链表即可
In [11]:
from utils import ListNode
from utils import array2listnode
from utils import listnode2array

class Solution:
    def removeDuplicateNodes(self, head: ListNode) -> ListNode:
        '''
        执行用时: 84 ms , 在所有 Python3 提交中击败了 78.10% 的用户
        内存消耗: 19.9 MB , 在所有 Python3 提交中击败了 100.00%

        '''
        if not head:
            return head
        l4 = head
        stack = {head.val}
        while l4.next:
            n = l4.next
            if n.val not in stack:
                stack.add(n.val)
                l4 = l4.next
            else:
                l4.next = l4.next.next
                
        return head

s = Solution()
assert listnode2array(s.removeDuplicateNodes(array2listnode([1, 2, 3, 3, 2, 1]))) == [1, 2, 3]
assert listnode2array(s.removeDuplicateNodes(array2listnode([1, 1, 1, 1, 2]))) == [1, 2]