Leetcode 82/83 remove duplicates from sorted list I&II [Python]
Reference of ListNode class:
class ListNode:
def __init__(self, x):
self.val = x
self.next = NoneI. 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 headThis 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 = curandcur = cur.next. This is just moving both pointer forward by one node. - In case
# 2 #:pre.next = cur.nextandcur = cur.next.We are NOT movingpreat all, but making it to point to the end of a sequence of some duplicating number. return dummy.next: Heredummy.nextis not necessarilyheadsince ifhead.valrepeats itself, it will be skipped in case# 2 #whenpre = dummy.
