This one is pretty simple if there is just one duplicate, but if there are multiple, using just one pointer won't work, because we need to skip multiple duplicates.
Going on solution from z3r0gravity7 from here https://leetcode.com/problems/remove-duplicates-from-sorted-list/discuss/1589369/Python3-intuitive-O(n)-solution-with-seeking-pointer-faster-than-98-(with-explanation) ->
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head == None or head.next == None: # handle edge cases where linked list has no or one nodes
return head
p = head # initialize current node pointer
while p.next: # until we have reached the last node (where next pointer is None)
seek = p.next # seek pointer is initialized to the node after current node (guaranteed to be not None by while loop condition)
while p.val == seek.val: # while the seeking pointer points to a duplicate of the current node
seek = seek.next # keep seeking
if seek == None: # if the seeking pointer has reached the end of the LL
p.next = None # then all nodes after the current node are duplicates, can truncate the LL after the current node
return head
# the seeking node is at the first non-duplicate node (may not have moved at all, if there were no duplicates)
p.next = seek # skip over all duplicate nodes (if any) by forwarding the next pointer of the current node to the seeked to node
p = p.next
return head
We can make it a bit more readable using suggestions from Elements of Programming interviews, and then we get:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
first = head
while first:
second = first.next
while second and first.val == second.val:
second = second.next
# skip over all duplicate nodes
first.next = second
first = first.next
return head
In the end it's kinda simple.
As usual it's really best to just work out the whole thing on paper, code will just get in the way.
I'm new to the grind, the hardest thing so far is to just stick to it.
Top comments (0)