给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为
, 返回
.
给出的链表为
, 返回
.
例如：
给出的链表为
给出的链表为
数据范围：链表长度 
，链表中的值满足 
要求：空间复杂度 )
，时间复杂度
进阶：空间复杂度 )
，时间复杂度
[编程题]删除有序链表中重复的元素-II
给重复的加一个标记，循环完把自己也删掉
class Solution: def deleteDuplicates(self , head: ListNode) -> ListNode: # write code here x = None dummy = ListNode(0) dummy.next = head p1 = dummy p2 = head while p2 and p2.next: while p2.next and p2.val == p2.next.val: x = p2 p2.next = p2.next.next if x: p2 = p2.next p1.next = p2 x = None else: p1 = p2 p2 = p2.next return dummy.next
发表于 2023-03-09 16:39:48
回复(0)
class Solution: def deleteDuplicates(self , head: ListNode) -> ListNode: if head is None&nbs***bsp;head.next is None: return head dummy = ListNode(-1) dummy.next, last, cur = None, None, head while cur: next_node = cur.next if next_node: if next_node.val == cur.val: val = cur.val while cur: if cur.val == val: cur = cur.next else: break else: if last is None: dummy.next = cur last = cur else: last.next = cur last = last.next cur = cur.next last.next = None else: if last is None: dummy.next = cur last = cur else: last.next = cur last = last.next cur = cur.next last.next = None return dummy.next
发表于 2022-09-09 00:42:20
回复(0)
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def deleteDuplicates(self , head: ListNode) -> ListNode: # write code here L=ListNode(None) temp=ListNode(1) L.next=temp d=dict() while head: if not d.get(head.val): d[head.val]=1 else: d[head.val]+=1 head=head.next for index,val in d.items(): if val==1: temp.next=ListNode(index) temp=temp.next return L.next.next
发表于 2022-08-18 19:43:06
回复(0)
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
# write code here
if not head:
return None
if not head.next:
return head
dic = {}
while head:
if head.val in dic:
dic[head.val] = 0
else:
dic[head.val] = 1
head = head.next
a = dic.items()
res = []
if len(a)==1:
return None
for i,j in a:
if j==0:
None
elif j==1:
res.append(i)
m = ListNode(res[0])
rt = m
for i in range(1,len(res)):
tmp = ListNode(res[i])
rt.next = tmp
rt = tmp
return m
发表于 2022-07-26 02:47:22
回复(0)
class Solution: def deleteDuplicates(self , head: ListNode) -> ListNode: pre = ListNode(-1) prehead = pre cur = head while cur: temp = cur.val mark = 1 while cur.next and cur.val == cur.next.val: mark = 0 cur.next = cur.next.next if mark: pre.next = ListNode(cur.val) pre = pre.next cur = cur.next return prehead.next
发表于 2022-07-18 23:57:03
回复(0)
# class ListNode: # def __init__(self, x): # self.val = x # self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # class Solution: def deleteDuplicates(self , head: ListNode) -> ListNode: # write code here ''' 升序排序的列表，记录上一个节点，比较当前节点和下一个节点值，如果一样，则当前节点下移，继续比较，直到不一样， 则上一个节点暂时指向当前节点，继续循环比较 ''' if head is None or head.next is None: return head # 首先确定新的 head。特征： front = None curNode = head nextNode = curNode.next head = None newHead = None curV = curNode.val nextV = nextNode.val # 寻找有效节点 while True: if curV != front and curV != nextV: if head is None: head = curNode newHead = head head.next = None else: head.next = curNode head = head.next head.next = None frontNode = curNode front = frontNode.val curNode = nextNode if curNode is not None: curV = curNode.val else: break if nextNode is None: nextV = None else: nextNode = nextNode.next if nextNode is not None: nextV = nextNode.val else: nextV = None return newHead
发表于 2022-06-02 13:17:19
回复(0)
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
if not head:
return head
pre = ListNode(2022)
pre.next = head
res = pre
cur = head.next
while cur:
n = 0
while cur and pre.next.val == cur.val:
n += 1
cur = cur.next
if n == 0:
pre = pre.next
else:
pre.next = cur
if cur:
cur = cur.next
return res.next
发表于 2022-05-15 21:45:53
回复(0)
通过字典完成对数据频次的统计，然后生成链表
############# Methond 1 ##############
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @return ListNode类
#
# from collections import defaultdict
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
# 判断空链表和单值链表
if (not head)&nbs***bsp;(not head.next):
return head
# 通过列表生成链表
l = []
cur = head
while cur:
l.append(cur.val)
cur = cur.next
## 初试化字典
v = 0
dic = {k:v for k in l}
## 统计数值的频次
for i in l:
dic[i] += 1
## 生成新的列表。这里已经去除了多次出现的数据
l = []
for k, v in dic.items():
if v <= 1:
l.append(k)
# 通过列表生成链表
res = head = ListNode(0) ## 设置头结点，省去了条件判断
for i in range(0, len(l)):
res.next = ListNode(l[i])
res = res.next
return head.next
优化：
class ListNode: def __init__(self, x): self.val = x self.next = None # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # # @param head ListNode类 # @return ListNode类 # # from collections import defaultdict class Solution: def deleteDuplicates(self , head: ListNode) -> ListNode: # write code here # 判断空链表和单值链表 if (not head)&nbs***bsp;(not head.next): return head # 通过列表生成链表 l = [] cur = head while cur: l.append(cur.val) cur = cur.next ## 初试化 带有频次的字典 import collections dic = collections.Counter(l) ## 列表生成式 l = [k for k,v in dic.items() if v <= 1] # 通过列表生成链表 res = head = ListNode(0) ## 设置头结点，省去了条件判断 for i in range(0, len(l)): res.next = ListNode(l[i]) res = res.next return head.next
发表于 2022-04-10 10:19:12
回复(1)
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
if head is None:
return head
dummyhead = ListNode(0)
dummyhead.next = head
cur = dummyhead
pre = cur # 记录重复元素的前一位指针
flag = 0 # 重复标志位
while cur.next :
cur = cur.next # 向前走一步
while cur.next and cur.next.val == cur.val: # 判断重复
flag = 1
cur = cur.next
if flag == 1:
pre.next = cur.next # 去重
flag = 0
else:
pre = cur
return dummyhead.next
发表于 2022-03-08 12:27:08
回复(0)
class Solution:
def deleteDuplicates(self , head: ListNode) -> ListNode:
# write code here
if not head:
return head
res={}
while head:
if head.val not in res.keys():
res[head.val]=1
else:
res[head.val]+=1
head=head.next
final=[k for (k,v) in res.items() if v==1]
if len(final)==0:
return ListNode(1).next
head=ListNode(final[0])
dummy=head
for i in final[1:]:
head.next=ListNode(i)
head=head.next
return dummy
发表于 2022-01-14 11:14:55
回复(0)
o(1) space complexity solution:
# NC24 删除有序链表中重复的元素-II def deleteDuplicates(self, head: ListNode) -> ListNode: # 构造dummy，解决删除head问题 dummy = ListNode(-1) dummy.next = head prev, curr = dummy, head count = 0 # 重复次数 while curr: # 重复元素移动和count标记 while curr.next and curr.next.val == curr.val: count += 1 curr = curr.next if count == 0: prev = curr curr = curr.next # 重复处理，prev指向不变，变更next删除重复元素，count重置 else: prev.next = curr.next curr = curr.next count = 0 return dummy.next
发表于 2021-11-11 11:16:05
回复(0)
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
#
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
def deleteDuplicates(self , head ):
# write code here
#新建一个头指针
p = ListNode(0)
p.next = head
#保存头节点
pp = p
q = head
f = 0
while q:
#找到值前后不同的点
while q.next and q.next.val == q.val:
q = q.next
f = 1
#f=1 表示有重复的节点
if f==1:
p.next = q.next
q = q.next
f = 0
#f=0 表示没有重复的节点
q = q.next
return pp.next
# def __init__(self, x):
# self.val = x
# self.next = None
#
#
# @param head ListNode类
# @return ListNode类
#
class Solution:
def deleteDuplicates(self , head ):
# write code here
#新建一个头指针
p = ListNode(0)
p.next = head
#保存头节点
pp = p
q = head
f = 0
while q:
#找到值前后不同的点
while q.next and q.next.val == q.val:
q = q.next
f = 1
#f=1 表示有重复的节点
if f==1:
p.next = q.next
q = q.next
f = 0
#f=0 表示没有重复的节点
else:
#指针后移
p = qq = q.next
return pp.next
发表于 2021-09-12 10:46:12
回复(0)
问题信息
难度：
21条回答
1167收藏
25540浏览
通过挑战的用户
查看代码-
2023-02-17 15:00:23 -
2022-11-23 18:33:38 -
2022-10-10 18:07:32 -
2022-09-20 14:48:28
-
2022-09-19 13:26:26
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
