Leetcode – Remove Duplicates from Sorted List in Python

Spread the love

LeetCode is a widely recognized platform that provides a plethora of algorithmic problems suited for improving your problem-solving skills, and it’s widely used by coders to prepare for interviews. In this long article, we’ll focus on one such problem: ‘Remove Duplicates from Sorted List’.

Problem Statement

The ‘Remove Duplicates from Sorted List’ problem (LeetCode problem #83) states:

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

Here are a few examples for better understanding:

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

Understanding the Problem

The problem gives us a sorted linked list and asks us to remove all duplicates from it. Since the input list is sorted, all the occurrences of a duplicate element are adjacent to each other, making it easier to identify and delete duplicates.

We are to traverse the linked list, comparing the current node and the next node. If they are the same (i.e., there’s a duplicate), we change the next pointer of the current node to skip the next node, thereby deleting it from the list.

Approach to Solve the Problem

In Python, we can define a class for a linked list node and then apply a straightforward algorithm to remove duplicates.

Step 1: Define a Node Class

Firstly, we need to define a class for a linked list node, which contains a value and a pointer to the next node.

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

Step 2: Create a Function

We will create a function called deleteDuplicates that takes the head node of a linked list as its parameter:

def deleteDuplicates(head):

Step 3: Handle Edge Cases

If the list is empty or contains only one node, it doesn’t have any duplicates, and we can return it as it is.

def deleteDuplicates(head):
    if head is None or head.next is None:
        return head

Step 4: Remove Duplicates

We traverse the list, comparing the current node and the next node. If they are the same, we change the next pointer of the current node to skip the next node:

def deleteDuplicates(head):
    if head is None or head.next is None:
        return head

    current = head
    while current is not None and current.next is not None:
        if current.val == current.next.val:
            current.next = current.next.next
        else:
            current = current.next

    return head

Here’s how it works:

  • We start with the head node as the current node.
  • In each iteration of the while loop, we compare the current node and the next node.
  • If they are the same (i.e., there’s a duplicate), we change the next pointer of the current node to skip the next node, thereby deleting it from the list.
  • If they are different, we move on to the next node.

Finally, the function returns the head node of the duplicate-free list.

Testing the Solution

Testing the solution would require setting up the linked list manually, which is a bit more complex compared to simple inputs. Here is how you can do it:

# Setting up a list: 1->1->2->3->3
head = ListNode(1)
head.next = ListNode(1)
head.next.next = ListNode(2)
head.next.next.next = ListNode(3)
head.next.next.next.next = ListNode(3)

# Removing duplicates
head = deleteDuplicates(head)

# Printing the list
current = head
while current is not None:
    print(current.val, end=' ')
    current = current.next
# Output: 1 2 3

Conclusion

The ‘Remove Duplicates from Sorted List’ problem is an excellent exercise for understanding linked list manipulation in Python. By methodically traversing the linked list and adjusting the ‘next’ pointers, we can effectively remove duplicate elements.

Leave a Reply