LeetCode----Remove Duplicates from Sorted List II

来源:互联网 时间:1970-01-01

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,

Given

1->2->3->3->4->4->5
, return
1->2->5
.

Given
1->1->1->2->3
, return
2->3
.

分析:

删除链表中所有重复的元素。

使用集合记录所有重复过的元素,然后再次遍历链表,将不在重复集合中的节点加入新的链表。时间复杂度为O(n),空间也为O(n)。

当然,也可以每次遍历找出非重复的元素,然后添入新的链表,这样空间满足O(1),但是时间为O(n^2).

代码:

class Solution(object): def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""p = headv = set() # record all the valuesd = set() # record only the duplicate valueswhile p: if p.val not in v:v.add(p.val) else:d.add(p.val) p = p.nextp = headr = q = ListNode(-1)while p: if p.val not in d:q.next = pq = q.next p = p.next q.next = Nonereturn r.next



相关阅读:
Top