Remove Duplicates from Sorted List

main.md

Remove Duplicates from Sorted List

Question on Leetcode - Easy

Approach

(high level summary)

The approach taken was to use two pointer method: one that takes account of the current value and the other to take the value ahead. Then I traversed through the linkedlist.

First, I use a while loop to iterate over each node in the linked list. It will continue until the current variable reaches the end of the list (i.e., None). Inside this while loop, another variable, temp is initialized with the next node after the current node (curr). This temp variable is used to check for duplicate values.

The second while loop is used to traverse the remaining nodes in the linked list, starting from the temp node. If a duplicate value is found, the temp variable is updated to the next node (temp.next), effectively skipping all nodes with the same value as the current node.

Finally, when the traversal of the linked list is complete, the function returns the modified linked list, which now contains no duplicate values.

Code

# 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: Optional[ListNode]) -> Optional[ListNode]:
        curr = head
        while curr is not None:
            temp = curr.next
            while temp is not None and temp.val == curr.val:
                temp = temp.next
            curr.next = temp
            curr = temp
        return head

Complexities

• Time complexity: O(n)
• Space complexity: O(1)