移除重复节点.md

面试题 02.01. 移除重复节点

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]范围内。
进阶：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

判断next的val是不是已经在节点中了
如果没有，就加入，cur=cur.next
否则cur.next=cur.next.next

python代码

执行用时： 88 ms , 在所有 Python3 提交中击败了 44.12% 的用户 内存消耗： 20.8 MB , 在所有 Python3 提交中击败了 18.97% 的用户

# 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:
        vals=set()
        if(not head):
            return head
        vals.add(head.val)
        cur=head
        while(cur.next):
            if(cur.next.val not in vals):
                vals.add(cur.next.val)
                cur=cur.next #下一个节点入set
            else:
                cur.next=cur.next.next #跳过下一个节点
        return head