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’.
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:
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
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.