Dare2Solve
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.
Dummy Node Initialization: Use a dummy node to handle cases where the head itself might be removed due to duplicates.
Traversal and Removal:
prev
) to keep track of the node before the current node being checked.curr
) to traverse through the list.curr.next
exists and has the same value as curr
), remove all nodes including curr
that have duplicate values.prev.next
directly to the next node after the duplicates are removed.Edge Cases:
None
to terminate the list.Return: Return dummy.next
, which points to the head of the modified linked list.
##Time Complexity:
O(n), where n is the number of nodes in the linked list. We traverse the list once.
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;
}
};
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
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;
}
}
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
};