难度:简单
知识点:链表
地址: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]范围内。
进阶:
如果不得使用临时缓冲区,该怎么解决?
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]
head.next
是否出现在哈希表中,如果出现过,则 head.next = head.next.next
跳过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]