Remove Duplicates From Sorted List - Leetcode Solution

Problem Statement: Given a sorted linked list, delete all duplicates such that each element appear only once.

Example 1:

Input: 1->1->2 Output: 1->2

Example 2:

Input: 1->1->2->3->3 Output: 1->2->3

Solution: To remove duplicates from a sorted linked list, we can traverse through the list and compare each node's value with its previous node's value. If they are the same, delete the duplicate node.

1. If the given linked list is empty or has only one node, return the head node as it is.
2. Initialize two pointers, current_node and previous_node, to the head node of the linked list. Set previous_node to None initially.
3. Traverse the linked list using current_node, comparing each node's value with its previous node's value.
4. If the values are the same, delete the current_node by removing its reference in the linked list.
5. If the values are different, move both current_node and previous_node one step forward.
6. Return the head node of the modified linked list.

Code:

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

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return None
        current_node = head
        previous_node = None
        while current_node:
            if previous_node and current_node.val == previous_node.val:
                previous_node.next = current_node.next
            else:
                previous_node = current_node
            current_node = current_node.next
        return head

Time Complexity: O(n), where n is the number of nodes in the linked list. Space Complexity: O(1), as we are only using two pointers to modify the linked list in place.

1