塞进裤子ヾ(≧O≦)〃嗷~

0%

删除链表中重复的结点

注意

书上有个如何在o(1)情况下删除结点的问题


最初思路:
使用一个额外的list记录出现的元素,遍历,再遇到相同的就删除。
有个问题:如何删除第一次出现的元素?
先遍历一遍,用list保存所有元素;
再遍历一遍,如果在list里出现次数大于1,就删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
def deleteDuplication(self, pHead):
if pHead == None:
return pHead
temp = [] #保存所有的元素
p = pHead

while p != None:
temp.append(p.val)
p = p.next
p = pHead
while p != None:
if temp.count(p.val) > 1: #是重复元素
pHead = self.delNode(pHead,p)
p = p.next
return pHead

def delNode(self, pHead, pnode):
if pHead == pnode:#删除头结点
return pHead.next
p = pHead
if p.next != pnode:
p = p.next
p.next = p.next.next
return pHead

以上的代码没注意到是排序的数组

不使用辅助list

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def deleteDuplication(self, pHead):
# write code here
if pHead == None:
return pHead
p = pHead
first =ListNode(-1)
first.next = p #
pre = first #pre是当前结点的前一个位置
# 如果phead是重复结点
while p != None and p.next != None:
if p.val == p.next.val:
tempval = p.val
while p and p.val == tempval:
p = p.next
pre.next = p #直接跳过重复的结点
else:
pre = p
p = p.next
return first.next
if help:小手一抖点个广告 or 大手一挥资助一下