Welcome back, part of my Self Development Goals for 2021 is “Complete at least 25 - 50 Leetcode Questions”, today we are going to discuss and solve Remove Duplicates from Sorted List
The solution to this question is very similar to the last post Leetcode 10 / 25 Post: Remove Linked List Element , so please check that out for more details. We can do it in O(n) time and O(1) space by just switching pointers. Since the list is sorted we know the duplicate elements will appear one after each other, its a case of checking for the value and moving the next pointer until we reach the end of the list.
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: """ Time Complexity: O(n) Space Complexity: O(1) """ if head == None: return None p1 = head while p1.next != None: if p1.next.val == p1.val: p1.next = p1.next.next else: p1 = p1.next return head
Time / Space Complexity
Why: We need to transverse the entire linked list in order to remove every duplicate element. Space: O(1)
Why: We are just switching pointers to remove elements so its constant space.
I hope you enjoyed this second post on solving some Leetcode problems, Anyway, that is 11 / 25 for my yearly goal done! now onto the rest, i hope you enjoyed this post!
Until next time