题目
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1： 
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列
思路1
遍历两次，第一次遍历的时候声明一个set集合，存储所有出现过多次的节点，在第二次遍历的时候使用双指针，cur指针在前，pre指针在后，如果发现cur指向的节点在集合中，则将cur向后移动，否则移动pre和cur节点
最终返回事先声明的dom节点，因为head节点指向的值可能多次出现，这里我们不可以直接返回head
复杂度
时间复杂度:
遍历了两次， O ( 2 n ) O(2n)O(2n)
空间复杂度:
存储了出现两次的节点， O ( n ) O(n)O(n)
Code2
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: s = set() if not head: return head pre,cur = ListNode(),head dom = pre while cur.next: if cur.val == cur.next.val: s.add(cur.val) cur = cur.next cur = head while cur: while cur and cur.val in s: cur = cur.next pre.next = cur if not cur: break cur = cur.next pre = pre.next return dom.next
思路2
只声明一个指针cur，在while循环中判断cur.next和cur.next,next是否存在。如果这两个值不等，说明cur.next是不重复出现的，可以当作cur的下一个节点；
否则说明这两个数一样，则这两个数需要去除，我们这里进一个while循环，不断推进cur.next的值，知道cur.next的值得不是最开始出现的那两个相同的数，如果他是none，则此时cur.next就是none，不需要额外操作，如果他是一个数字，且后面还有节点，则继续循环
复杂度2
时间复杂度:
遍历一次： O ( n ) O(n)O(n)
空间复杂度:
没有声明额外空间： O ( 1 ) O(1)O(1)
Code2
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]: cur = dumy = ListNode(next=head) while cur.next and cur.next.next: val = cur.next.val if val == cur.next.next.val: while cur.next and cur.next.val == val: cur.next = cur.next.next else: cur = cur.next return dumy.next
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)