Remove Duplicates From Sorted List Leetcode Problem 83 [Python Solution]

Are you ready for the Remove Duplicates From Sorted List Leetcode Problem? No pressure, it is a relatively easy problem, falling under the category of linked list challenges.

The problem statement can be found on LeetCode.

Here’s the problem we’re dealing with:

Problem: Given the head of a sorted linked list, delete all duplicates so that each element appears only once.

After removing the duplicates, return the sorted linked list.

Before diving into the solution, let’s break down the problem step by step.

Problem Overview

The task at hand is to remove duplicates from a sorted linked list.

To illustrate, let’s consider a couple of examples.

Example 1:

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

In this example, we have a sorted linked list with duplicate values.

We need to remove the duplicates and return the list sorted.

Example 2:

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

In this case, the linked list has multiple duplicates, and our goal is to eliminate them while maintaining the sorted order.

Constraints:

The number of nodes in the list is in the range [0, 300].
The value of Node.val falls within the range of -100 to 100.
The list is guaranteed to be sorted in ascending order.

Now, let’s discuss the constraints, which are essential to consider when designing our solution.

Understanding the Constraints

The problem constraints provide valuable information that can guide our solution.

Here’s a brief analysis of each constraint:

Number of Nodes: The linked list can have between 0 and 300 nodes.

This implies that our solution should be efficient enough to handle a wide range of input sizes.

Node Value Range: The values in the linked list nodes are within the range of -100 to 100. This constraint helps us understand the nature of the data we are dealing with.
Sorted List: The list is sorted in ascending order, which simplifies our task.

We can leverage this ordering to efficiently remove duplicates.

Now that we’ve grasped the problem and constraints, let’s move on to the solution.

Remove Duplicates From Sorted List LeetCode Problem Solution

1. Bruteforce Approach

Before we dive into the efficient solution, let’s briefly explore a brute-force approach that helps us understand the problem better.

While not the most efficient solution, it’s a good starting point for our journey.

def deleteDuplicates(head):
    current = head

    while current:
        while current.next and current.next.val == current.val:
            current.next = current.next.next
        current = current.next

    return head

In the brute-force approach, we initialize a pointer current at the head of the linked list.

We then use nested loops to traverse the list.

The outer loop (while current) moves the current pointer through the list.

The inner loop (while current.next and current.next.val == current.val) identifies and removes duplicates.

However, this approach, while functional, is not the most efficient way to solve the problem.

We’re iterating through the list multiple times, resulting in a time complexity of O(n^2) in the worst case.

Let’s explore a more efficient approach next.

2. An Efficient Approach – Keeping Unique Values

To solve this problem efficiently, we can utilize the fact that the linked list is sorted.

This allows us to iterate through the list just once, removing duplicates as we encounter them.

Here’s the Python solution for this efficient approach:

def deleteDuplicates(head):
    current = head

    while current:
        if current.next and current.next.val == current.val:
            current.next = current.next.next
        else:
            current = current.next

    return head

This efficient approach involves a single pass through the linked list.

We maintain the current pointer and check if the next node’s value is the same as the current node.

If it is, we skip the next node by updating the current.next pointer.

If the values are different, we move the current pointer to the next node.

This approach ensures that we remove duplicates in a single pass, resulting in a time complexity of O(n), where n is the number of nodes in the linked list.

It’s a highly optimized solution.

Python Code Solution

Now that we’ve explored both a brute-force and an efficient approach in detail, let’s provide the Python solution using the efficient approach:

View on GitHub ➹

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    current = head

    while current:
        if current.next and current.next.val == current.val:
            current.next = current.next.next
        else:
            current = current.next

    return head

This code defines a ListNode class to represent the nodes of a linked list.

The deleteDuplicates function takes the head of the linked list as input and returns the head of the modified list with duplicates removed.

Time and Space Complexity

It’s essential to analyze the time and space complexity of our solution to understand its efficiency.

Time Complexity: The time complexity of our efficient approach is O(n), where n is the number of nodes in the linked list.

We iterate through the list once, removing duplicates in a single pass.

Space Complexity: The space complexity is O(1) because we don’t use any additional data structures that depend on the input size.

We only maintain a few pointers.

Reasoning Behind Our Approach

The reasoning behind our efficient approach lies in the sorted nature of the linked list.

Since the list is sorted, duplicates are guaranteed to be adjacent to each other.

Therefore, we can traverse the list once, and when we encounter duplicates, we simply bypass them.

This approach minimizes the number of operations and results in an optimal time complexity.

Conclusion

In this guide, we explored the LeetCode problem Remove Duplicates From Sorted List We discussed the problem statement, constraints, and various approaches to solving the problem.

While we briefly introduced a brute-force approach, our main focus was on an efficient solution that leverages the sorted nature of the linked list.

This efficient approach allows us to remove duplicates in a single pass, resulting in a time complexity of O(n), where n is the number of nodes in the list.

I hope you found this guide helpful in understanding and solving the problem.

If you have any questions or suggestions, please feel free to comment and share your thoughts.

Learning and mastering data structures and algorithms is a rewarding journey, and I encourage you to keep practicing and exploring more coding challenges.

For the full problem statement and to try out the solution on LeetCode, you can visit the problem link.

Thank you for joining me in this coding adventure, and happy coding!