Removing duplicate elements from a sorted linked list involves eliminating nodes with repeated occurrences of similar elements while maintaining the sorted order of the list.
In order to remove duplicates, we traverse through the linked list one node at a time while checking is the next node’s value is same a current node. If the next node’s value is same as the current node’s value, we skip/delete the next node and point the current node’s reference to next next node.
Below is the code to remove duplicates in a sorted linked list:
def remove_duplicates(head):
if not head or not head.next:
# If the list is empty or has only one node
# It means there are no duplicates to remove
return head
current = head
# Traverse until we reach the end of linked list
while current != None and current.next != None:
if current.item == current.next.item:
# Current node's item is the same as the next node's item
# It means that the next node is a duplicate
# We need to skip/remove the next node by
# Changing the current node's next pointer to next next node
current.next = current.next.next
else:
# Next node is different from current ndoe
# so we can move to it
current = current.next
# Example usage:
# Assuming 'head' is the head of the linked list
remove_duplicates(head)