Remove Duplicates from Sorted List
Given the HEAD
of the Sorted Linked List. delete all duplicates such that each element appears only once. Return the Head of the Modified Linked List.
So the output will look like [1]->[2]->[3]. Let's initialize our curr
pointer starting from the HEAD
.
Intuition
curr
pointer at the HEAD
and automatically curr.next
is the Node next to it. So we need to compare the current node values and next node value every time until all the duplicate nodes got removed. Let's take a sneak peak of the initialization code.
# 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]:
curr = head
But if the HEAD
is NULL or there is only one node in the Linked List, we need to return the HEAD
without any further operation. Let's get the code-template ready.
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
curr = head
while curr and curr.next:
pass
return head
Now Let's find the duplicate nodes and start removing them iteratively.
while curr and curr.next:
# if current node value and next node value is equal
if curr.val == curr.next.val:
# Linking with the next of the next node
curr.next = curr.next.next
Now you can see the value of curr
node and curr.next
node is not equal. Now the curr
pointer will move forward to it's next node.
while curr and curr.next:
# if current node value and next node value is equal
if curr.val == curr.next.val:
# Linking with the next of the next node
curr.next = curr.next.next
else:
# moving curr pointer to it's next pointer
curr = curr.next
Let's visualize the rest of the iterations
Now the curr.next
has reached to NULL
and break out of the while loop. The output will look like this
Let's see the complete code snippet bellow.
Complete Code Snippet
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
curr = head
while curr and curr.next:
if curr.val == curr.next.val:
curr.next = curr.next.next
else:
curr = curr.next
return head
Thanks for Stopping by! Happy Leet coding
Connect with me on