Given a sorted list of numbers in a linked list we want to remove all occurrence of duplicates and return a list with out them. Note that we need to delete the number that is repeated altogether without leaving one.
Example:
[1, 2, 3, 3, 4, 4,4,4,5]
Ans:
[1,2,5]
Solution:
We can have two pointers , curr and prev.
The curr pointer will move to the end of the repeating sub array while the prev pointer is staying at the beginning of the repeating sub array.
Then we break the link to set the next of the prev pointer to the next of curr pointer and by doing so we delete all the occurrences of a the repeating numbers.
We shall repeat the above step as long as the curr pointer doesn’t reach the end.
public ListNode DeleteDuplicates(ListNode head)
{
if (head == null || head.next == null) return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode current = head;
while (current != null) {
while (current.next != null && current.val == current.next.val) {
current = current.next;
}
if (prev.next == current) {
prev = prev.next;
} else {
prev.next = current.next; //this deletes of repeated numbers
}
current = current.next;
}
return dummy.next;
}