LinkedList:Remove Duplicates from Sorted List

 

Approach

1. Traverse the List: Iterate through the linked list.
2. Check for Duplicates: Compare the current node with the next node.
3. Remove Duplicates: If duplicates are found, adjust pointers to remove the duplicate nodes.
4. Continue: Move to the next node and repeat until the end of the list.

Explanation

1. ListNode Struct: This defines the structure for the linked list nodes.

2. removeDuplicates Function:

   • Traverse the list with a pointer current.
   • If current->val is the same as current->next->val, then adjust pointers to remove the duplicate node and free its memory.
   • If no duplicate is found, move current to the next node.

3. Helper Functions:

   • printList is used to display the linked list.
   • createNode is a convenience function to create new nodes.

4. Main Function:

   • Creates a sample sorted linked list with duplicates.
   • Prints the list before and after removing duplicates.
   • Cleans up allocated memory.

This method efficiently removes duplicates from a sorted linked list in linear time, $O(n)$, where $n$ is the number of nodes in the list.

ListNode* deleteDuplicates(ListNode* head) {

if(!head || !head->next)

return head;

ListNode* cur = head;

while(cur->next){

if(cur->val == cur->next->val){

ListNode* tmp = cur->next;

cur->next = cur->next->next;

delete tmp;

}

else {

cur = cur->next;

}

}

return head;

}