053.md

83. Remove Duplicates from Sorted List

Difficulty: 🟢 Easy

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Examples:

Example 1:

Input: head = [1,1,2]
Output: [1,2]

Example 2:

Input: head = [1,1,2,3,3]
Output: [1,2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• 100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

Solutions

O(n) solution

# 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]:
        pointer = head
        while pointer and pointer.next:
            if pointer.val == pointer.next.val:
                pointer.next = pointer.next.next
                continue
            pointer = pointer.next
        return head

The given solution approach removes duplicates from a sorted linked list. It follows these steps:

1. Initialize a pointer pointer to the head of the linked list.
2. Iterate through the linked list using the pointer and pointer.next pointers.
3. If the value of pointer is equal to the value of pointer.next, it means there is a duplicate.
   • Skip the duplicate by updating pointer.next to pointer.next.next.
   • Continue to the next iteration.
4. If the values are not equal, move the pointer to the next node.
5. Return the head of the modified linked list.

Complexity Analysis

The time complexity of the algorithm is O(n), where n is the number of nodes in the linked list. In the worst case, we traverse through all the nodes of the linked list once.

The space complexity of the algorithm is O(1) since it uses a constant amount of additional space.

Summary

The given solution removes duplicates from a sorted linked list. It iterates through the linked list, skips duplicates by updating the pointers, and returns the head of the modified linked list. The algorithm has a time complexity of O(n) and a space complexity of O(1).

NB: If you want to get community points please suggest solutions in other languages as merge requests.