🎨Now live: Try our Free AI Image Generation Feature

Intuition
We need to traverse the linked list and remove nodes with duplicate values. After removing duplicates, the linked list should only contain nodes with unique values in sorted order.
Approach
- Dummy Node Initialization: Use a dummy node to handle cases where the head itself might be removed due to duplicates.
- Traversal and Removal:
- Initialize a pointer (
prev
) to keep track of the node before the current node being checked. - Use another pointer (curr
) to traverse through the list. - Whenever a duplicate is found (i.e.,curr.next
exists and has the same value ascurr
), remove all nodes includingcurr
that have duplicate values. - Connectprev.next
directly to the next node after the duplicates are removed. - Edge Cases:
- Handle cases where duplicates exist at the beginning, middle, or end of the list.
- Ensure the last node is properly connected to
None
to terminate the list. - Return: Return
dummy.next
, which points to the head of the modified linked list.
Complexity
##Time Complexity:
O(n), where n is the number of nodes in the linked list. We traverse the list once.
Space Complexity: O(1), since we use only a constant amount of extra space regardless of the input size.
Code
C++
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* output = new ListNode(0, head);
ListNode* pre = output;
while (head) {
if (head->next && head->val == head->next->val) {
while (head->next && head->val == head->next->val) {
head = head->next;
}
pre->next = head->next;
} else {
pre = pre->next;
}
head = head->next;
}
return output->next;
}
};
Python
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
output = ListNode(0, head)
pre = output
while head:
if head.next and head.val == head.next.val:
while head.next and head.val == head.next.val:
head = head.next
pre.next = head.next
else:
pre = pre.next
head = head.next
return output.next
Java
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode output = new ListNode(0, head);
ListNode pre = output;
while (head != null) {
if (head.next != null && head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
pre.next = head.next;
} else {
pre = pre.next;
}
head = head.next;
}
return output.next;
}
}
JavaScript
var deleteDuplicates = function(head) {
if(!head || !head.next) {
return head
}
let output = new ListNode(0, head), pre = output
while(head) {
if(head.next && head.val === head.next.val) {
while(head.next && head.val === head.next.val) {
head = head.next
}
pre.next = head.next
} else {
pre = pre.next
}
head = head.next
}
return output.next
};