在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5
数据范围：链表长度满足 
，链表中的值满足 
进阶：空间复杂度 %5C)
，时间复杂度 %20%5C)
例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：
[编程题]删除链表中重复的结点
class Solution:
def deleteDuplication(self, pHead):
# write code here
res1 = []
res2 = []
while pHead:
if pHead.val not in res1:
res1.append(pHead.val)
elif pHead.val not in res2:
res2.append(pHead.val)
pHead = pHead.next
dummy = ListNode(0)
pre = dummy
for i in res1:
if i not in res2:
node = ListNode(i)
pre.next = node
pre = pre.next
return dummy.next
def deleteDuplication(self, pHead):
# write code here
res1 = []
res2 = []
while pHead:
if pHead.val not in res1:
res1.append(pHead.val)
elif pHead.val not in res2:
res2.append(pHead.val)
pHead = pHead.next
dummy = ListNode(0)
pre = dummy
for i in res1:
if i not in res2:
node = ListNode(i)
pre.next = node
pre = pre.next
return dummy.next
发表于 2021-05-08 20:34:43
回复(0)
class Solution: def deleteDuplication(self, pHead): temp = [] while pHead: temp.append(pHead.val) pHead = pHead.next #把列表中数量大于1的元素删除 temp = list(filter(lambda i:temp.count(i)==1, temp)) #把这些元素串成链表 newHead = ListNode(0) p = newHead for i in temp: p.next = ListNode(i) p = p.next return newHead.next
发表于 2021-04-29 18:10:16
回复(0)
写了好久……实力还是不行
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteDuplication(self, pHead): # write code here cur=p=ListNode(-1) cur.next=pHead runner=pHead while runner and runner.next: if runner.val==runner.next.val: val=runner.val while runner and val==runner.val: runner=runner.next cur.next=runner else: cur=runner runner=runner.next cur.next=runner return p.next
发表于 2021-04-14 11:27:10
回复(0)
python解法：
解法1:需要设一个前驱结点；
class Solution: def deleteDuplication(self, pHead): res = ListNode(-1) # 添加一个头结点； res.next = pHead pre = res # pre味前驱结点； p = pHead while p: if p.next and p.val == p.next.val: # 发现重复元素 p = p.next while p.next and p.val == p.next.val: # 找到最后一个重复元素 p = p.next p = p.next pre.next = p # 把前驱结点指向不重复结点； else: pre = p p = p.next return res.next
编辑于 2021-02-24 12:29:13
回复(0)
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteDuplication(self, pHead): pTemp = [] pNode =[] while pHead: if pHead.val in pTemp: if pNode !=[]: pNode.pop(-1) else: pTemp.append(pHead.val) pNode.append(pHead) pHead = pHead.next if pNode !=[]: for i in range(len(pNode)-1): pNode[i].next = pNode[i+1] pNode[-1].next = None return pNode[0] else: return None # write code here
发表于 2021-02-23 08:43:04
回复(0)
class Solution: def deleteDuplication(self, pHead): # write code here # 0&nbs***bsp;1 node if not pHead&nbs***bsp;not pHead.next: return pHead # >=2 nodes tmp = ListNode(-1) tmp.next = pHead cur = -1 while tmp.next and tmp.next.next: if tmp.next.val == tmp.next.next.val: # update cur cur = tmp.next.val # find all match nodes while tmp.next.val == cur: # last node if not tmp.next.next: tmp.next = None break else: tmp.next = tmp.next.next # in case head is changed if tmp.val == -1: pHead = tmp.next else: tmp = tmp.next return pHead
发表于 2020-09-10 17:42:00
回复(0)
思路：在链表最前方加一个表头
1.两个指针，pre和p
2.当p和p.next相同时，循环p和p.next的值直到不相等，此时pre.next指向p.next，删除了中间重复的部分
3.一头一尾有重复的，有一点注意的是，在python里会产生None，此时没有None.next和None.val，因此记住及时推出循环
class Solution:
def deleteDuplication(self, pHead):
# write code here
if pHead == None :
return pHead
newHead = ListNode(-1)
pre = newHead
newHead.next = pHead
p = pHead
while p and p.next:
if p.val == p.next.val:
while p.val == p.next.val and p.next:
p = p.next
if p.next == None:
break
p = p.next
pre.next = p
else:
pre = p
p = p.next
return newHead.next
发表于 2020-09-06 00:15:01
回复(0)
class Solution:
def deleteDuplication(self, pHead):
# write code here
new=ListNode(0)
A={}
old=pHead
while pHead:
if pHead.val not in A:
A[pHead.val]=0
else:
A[pHead.val]+=1
pHead=pHead.next
pre=new
print(A)
while old:
if (A[old.val]>0) or(old.next and old.val==old.next.val):
pre.next=old.next
old=old.next
else:
pre.next=old
old=old.next
pre=pre.next
return new.next
编辑于 2020-09-05 09:22:52
回复(0)
class Solution: def deleteDuplication(self, pHead): # write code here if not pHead: return None dummy = ListNode(-1) dummy.next = pHead pre = dummy cur = pHead while cur and cur.next: if cur.val == cur.next.val: value = cur.val while cur and cur.val == value: cur = cur.next pre.next = cur else: pre = cur cur = cur.next return dummy.next
发表于 2020-07-29 16:16:50
回复(0)
class Solution: def deleteDuplication(self, pHead): if not pHead: return pHead list_val = [] list_index = [] new = pHead index = 0 while new: if new.val not in list_val: list_val.append(new.val) list_index.append(index) else: list_index.append(-1) index += 1 new = new.next for i in range(len(list_index)-1): if list_index[i+1] == -1: list_index[i] = -1 i = 0 while list_index[i] == -1: if not pHead: pHead = pHead else: pHead = pHead.next i += 1 if i==len(list_index): break if not pHead: return pHead new = pHead tmp = new tmp1 = new if i+1==len(list_index): return tmp for j in list_index[i+1:]: tmp1 = tmp1.next if j != -1: new.next = tmp1 new = new.next tmp1 = tmp1.next new.next = tmp1 return tmp
发表于 2020-07-18 23:28:15
回复(0)
class Solution: def deleteDuplication(self, pHead): # write code here if pHead==None: return pHead p = ListNode(None) p.next = pHead q = p while q.next and q.next.next: if q.next.val != q.next.next.val: q = q.next else: t = q.next while t.next and t.val==t.next.val: t = t.next q.next = t.next return p.next
发表于 2020-07-07 23:49:36
回复(0)
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteDuplication(self, pHead): l1=[] if not pHead: return None while pHead: l1.append(pHead.val) pHead=pHead.next cl=[] for i in range(len(l1)): c=l1.count(l1[i]) cl.append(c) for i in range(len(l1)-1,-1,-1): if cl[i]>=2: l1.pop(i) if len(l1)==0: return None pl=[] for i in range(len(l1)): p=ListNode(l1[i]) p.next=None pl.append(p) if len(pl)==1: return pl[0] for i in range(len(pl)-1): pl[i].next=pl[i+1] return pl[0] # write code here
发表于 2020-05-28 00:41:45
回复(0)
class Solution:
def deleteDuplication(self, pHead):
# write code here
if pHead == None:
return None
t = pHead
vals = {}
while t!= None:
if vals.get(t.val)==None:
vals.update({t.val: True})
else:
vals.update({t.val: False})
t = t.next
# 特别要注意的如：{1,1,1,1,2,2,3,3}这种特殊情况
# create a new list
# last is a fake Node
head = ListNode(-1)
p = head
for i in vals.keys():
if vals[i]:
p.next = ListNode(i)
p = p.next
# no True elements in vals
if head.next == None:
return None
else:
head = head.next
return head 用了额外的存储空间（python中的字典）：将原链表中每个元素的值取出，以 {val: True/False}的格式存入字典，其中如果此前val存在则为False。最后重新生成一个链表，先造一个伪节点做头，将字典里为True的值取出并填入链表，如果伪节点的下一节点不为空，就移动它到下一节点，此时它就是真正的头结点；为空则说明链表生成失败了，无意义，所以返回None。
编辑于 2020-03-22 15:30:37
回复(0)
自己的思路 能实现 但是理解起来比较复杂
使用了 有头结点的链表 所以 最后没有返回头结点 因为做不做处理返回的都一样
def del_repeat(self): pro = self.head next = pro.next repeat = False while next.next: while next.data is next.next.data: repeat = True next = next.next pro.next = next if next.next.next is None: next = next.next pro.next = next break if repeat: next = next.next pro.next = next repeat = False if next is None: break else: pro = next next = next.next另外对 第一的那个解 做了 python版的代码 感觉自愧不如 人家的思路就是清晰
def del_same_node(self): pro = self.head next = pro.next while next: if next.next is not None and next.data is next.next.data: while next.next is not None and next.data is next.next.data: next = next.next pro.next = next.next next = next.next else: pro = pro.next next = next.next
发表于 2020-03-12 01:43:02
回复(0)
class Solution: def deleteDuplication(self, pHead): # write code here #三个指针 #一个用以保存当前的位置 #一个用以保存丢弃的数 #一个用以保存上一个数 rightnowpoint=pHead discardpoint="dis" lastpoint='unode' if pHead is None : return None while rightnowpoint.next is not None: if rightnowpoint.val==rightnowpoint.next.val: #重复-》直接丢弃 discardpoint=rightnowpoint.next.val #调整链表 rightnowpoint.next=rightnowpoint.next.next continue if rightnowpoint.val!=rightnowpoint.next.val: if rightnowpoint.val==discardpoint: #当前的得扔掉 if lastpoint=='unode': #表明是头结点 pHead=rightnowpoint.next #lastpoint=rightnowpoint.next rightnowpoint=rightnowpoint.next else: lastpoint.next=rightnowpoint.next rightnowpoint=rightnowpoint.next continue else: if lastpoint=='unode': #表明是头结点 pHead=rightnowpoint lastpoint=rightnowpoint else: lastpoint.next=rightnowpoint #修改当前的指针位置 lastpoint=lastpoint.next rightnowpoint=rightnowpoint.next #结束收尾 if rightnowpoint.val==discardpoint: if lastpoint=='unode': pHead=None else: lastpoint.next=None else: if lastpoint=='unode': #表明是头结点 pHead=rightnowpoint else: lastpoint.next=rightnowpoint return pHead
v2:
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteDuplication(self, pHead): # write code here #三个指针 #一个用以保存当前的位置 #一个用以保存丢弃的数 #一个用以保存上一个数 rightnowpoint=pHead discardpoint="dis" lastpoint='unode' if pHead is None : return None while rightnowpoint.next is not None: #一般情况 #不相同 if rightnowpoint.val!=rightnowpoint.next.val: if rightnowpoint.val !=discardpoint: if lastpoint is 'unode': lastpoint=rightnowpoint pHead=rightnowpoint else: lastpoint.next=rightnowpoint lastpoint=lastpoint.next else:#和丢弃的值相同，都扔掉 discardpoint=rightnowpoint.val rightnowpoint=rightnowpoint.next #相同 else: discardpoint=rightnowpoint.val rightnowpoint.next=rightnowpoint.next.next #结束 if rightnowpoint.val!=discardpoint: if lastpoint is 'unode': pHead=rightnowpoint else: lastpoint.next=rightnowpoint else: if lastpoint is 'unode': pHead=None else: lastpoint.next=None return pHead
编辑于 2020-03-05 10:05:05
回复(0)
- 要充分考虑头节点和第二个节点相同的情况
- 通过添加一个不同的头结点，避免上述情况
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def deleteDuplication(self,pHead):
"""
通过添加一个不同的头结点
:param pHead:
:return:
"""
# 头结点为空或者只有一个节点的情况
if pHead == None or pHead.next == None:
return pHead
else:
# create new head
pNewHead = ListNode(pHead.val - 1)
pNewHead.next = pHead
pre = pNewHead
cur = pNewHead.next
while(cur != None and cur.next != None):
if cur.val == cur.next.val :
while cur.next!=None and cur.val == cur.next.val:
cur = cur.next
cur = cur.next
pre.next = cur
else:
pre = pre.next
cur = cur.next
return pNewHead.next
p1 = ListNode(1)
p1.next = ListNode(2)
p1.next.next = ListNode(3)
p1.next.next.next = ListNode(3)
p1.next.next.next.next = ListNode(4)
p1.next.next.next.next.next = ListNode(4)
s= Solution()
ans = s.deleteDuplication2(p1)
ans
编辑于 2020-02-26 14:03:10
回复(0)
单层循环的简单解法
删除链表需要用到多个指针，比如上图中，我们想要删除节点q，只需要把p.next指向r即可。 所以我们使用3个指针，p代表前一个节点，q和r是后面两个节点，是每次循环时用来比较的。 首先，p保证与q的值不相等，因此只有当我们完成下面的一个数的操作（不论是保留还是删除），才会更新它。 比如最简单的情况，q与r不相等，那么我们直接移动指针即可（左图） 如果q与r相等呢？这时候我们需要继续往下寻找这个数的最后一个，所以不移动p，只移动q和r，直到q与r不相等时才停止。此时删除这些中间节点。 总结一下，我们只需要一直往下遍历q和r，如果他们不等，则有两种情况，一个是p的下一个就是q，那么就没有重复，更新p；如果p的下一个不是q，则说明有重复，这时更新p的next，删除节点。 这里还需要注意链表尾部是重复节点的问题，由于我们不知道什么时候会遇到最后一个重复的数，当循环结束时还没有遇到的情况，就无法执行更新p.next了，所以要在最后再进行一次判断，p与q不相连的话则需要删除它们。
class Solution: def deleteDuplication(self, pHead): head = ListNode(None) head.next = pHead p = head q = pHead # 输入为空 if not q: return None # 循环整个链表 while q.next: # 当 q 不等于 r 时 if q.val != q.next.val: # p 与 q 不相连，说明有重复 if q != p.next: p.next = q.next # p 与 q 相连，不处理，继续移动 p else: p = q q = q.next # 判断链表结尾是重复的问题 if q != p.next: p.next = q.next return head.next
发表于 2020-02-16 00:08:56
回复(0)
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: def deleteDuplication(self, pHead): # write code here if pHead==None&nbs***bsp;pHead.next==None: return pHead if pHead.val==pHead.next.val:#当前字符与下一个字符相同时 p=pHead.next.next while p and p.val==pHead.val:#跳过所有相同字符，从新的不同的开始 p=p.next return self.deleteDuplication(p) pHead.next=self.deleteDuplication(pHead.next)#当前字符与下一字符不同时 return pHead本题是一个递归的应用，对现有递归的判断分为两种，即当前字符与下一字符是否相同。通过这个判断分别进行不同的循环。直到链表中最多一个节点时。它相当于分成好多不同的重复段，每次都从不重复的地方进行新的开始
发表于 2020-01-27 23:46:59
回复(0)
# -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # 解题思路：添加一个头结点方便遍历，设置快慢指针p1和p2 # 快指针p2寻找重复节点，一旦找到重复节点，遍历到最后一个重复节点 # 慢指针p1的next指向p2的next，删除重复节点 # 重复上述过程只到快指针p2为None结束 class Solution: def deleteDuplication(self, pHead): # write code here if not pHead&nbs***bsp;not pHead.next: return pHead p = ListNode(0) p.next = pHead pHead = p del p p1 = pHead p2 = pHead.next while p2: if p2.next and p2.val == p2.next.val: while p2.next and p2.val == p2.next.val: p2 = p2.next p1.next = p2.next p2 = p2.next else: p1 = p1.next p2 = p2.next return pHead.next
发表于 2019-12-08 19:35:54
回复(0)
问题信息
难度：
59条回答
2579收藏
143198浏览
通过挑战的用户
查看代码-
2023-03-14 00:52:25 -
2023-03-08 18:59:35 -
2023-02-13 21:51:56 -
2022-11-12 17:37:39 -
2022-11-11 16:42:44
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
