Leetcode 82/83 remove duplicates from sorted list I&II [Python]

Yiwei Ni
Yiwei Ni
Aug 31, 2018 · 3 min read

Reference of ListNode class:

class ListNode: 
def __init__(self, x):
self.val = x
self.next = None

I. Keep one of the duplicates

input: 1->2->2->3->3->4

output: 1->2->3->4

class Solution: 
def deleteDuplicates(self, head):
cur = head
while cur:
if cur.next and cur.next.val == cur.val:
cur.next = cur.next.next
else:
cur = cur.next
return head

This one is pretty straight forward. We only need to check if the current node’s value is the same as its next node’s value. In order to do that, we keep a current node pointer. If the next node is not None and has the same value, we skip it by changing cur.next to cur.next.next . Otherwise, we keep updating the cur pointer to the next node.

In the end, we return head with all duplicates being skipped.

II. Keep only distinct nodes

input: 1->2->2->3->3->4

output: 1->4

Now it gets interesting. If a node’s value repeats in other nodes, we want to delete all of these nodes. In the previous question, we only need to look at the next node. However, in this case only looking at the next node is not enough. We have to compare with its previous value and keep a pointer at the previous value in case if we want to delete the current node. This include the head , and that’s why we add a dummy node and point it to the head.

Detailed explanation in the comments:

class Solution: 
def deleteDuplicates(self, head):
# add dummy and initialize all the pointers
dummy = ListNode(0)
dummy.next = head
pre = dummy
cur = head
while cur:
# if cur is not the last not and it has the same
# value as the next node, we update the cur pointer
while cur.next and cur.val == cur.next.val:
cur = cur.next

if pre.next == cur: # 1 #
# this means cur pointer is not updated in
# the while loop, thus cur's value is distinct
# we move pre pointer to the cur's location
pre = cur else: # 2 #
# cur's value has repeated itself so
# we skip the entire sequence of nodes with
# this value
pre.next = cur.next # and in either case we update the cur pointer
cur = cur.next # 3 #
return dummy.next

Notes:

  • In case # 1 # :pre = cur and cur = cur.next . This is just moving both pointer forward by one node.
  • In case # 2 # :pre.next = cur.next and cur = cur.next .We are NOT moving pre at all, but making it to point to the end of a sequence of some duplicating number.
  • return dummy.next : Here dummy.next is not necessarily head since if head.val repeats itself, it will be skipped in case # 2 # when pre = dummy .

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade