# Remove Duplicates from Sorted List II LeetCode Solution

Difficulty Level Medium

## Problem Statement

Remove Duplicates from Sorted List II LeetCode Solution – Given the `head` of a sorted linked listdelete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.

```Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]```

## Explanation

The idea here is to traverse our linked list and use two pointers:

1. `slow` is for node just before duplications begins
2. `fast` is for the last node of the duplication group.

Now, we traverse nodes and do the following steps:

1. while we have `fast.next` and its value is equal to `fast`, it means, that we have one more duplicate, so we move `fast` pointer to the right.
2. If it happens, that `slow.next` equal to `fast`, it means, that we have only `1` element in the group of duplicated elements, that is we do not need to delete it and we move both pointers to right.
3. If it happens, that `slow.next` is not equal to `fast`, it means, that we need to skip a group of duplicated elements: we create a new connection: `slow.next = fast.next`, and also we allocate `fast = slow.next`. Note, that now we still have the original property: `slow` points to the node before the group of duplicated elements and `fast` will be the last element of this group (after `while fast.next and fast.val == fast.next.val:` line)

Complexity: time complexity is `O(n)`: we traverse our list at most twice for each of the pointers. Space complexity is `O(1)`: we did not use any additional memory here.

## Code

### C++ Code for  Remove Duplicates from Sorted List II

```class Solution {
public:
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
int duplicate;
while (cur->next && cur->next->next) {
if (cur->next->val == cur->next->next->val) {
duplicate = cur->next->val;
while (cur->next && cur->next->val == duplicate) {
cur->next = cur->next->next;
}
}
else {
cur = cur->next;
}
}
return dummy->next;
}
};```

### Java Code for  Remove Duplicates from Sorted List II

```class Solution {
while(cur!=null){
while(cur.next!=null&&cur.val==cur.next.val){
cur=cur.next;
}
if(pre.next==cur){
pre=pre.next;
}
else{
pre.next=cur.next;
}
cur=cur.next;
}
}
}```

### Python Code for  Remove Duplicates from Sorted List II

```class Solution:
dummy = ListNode(-1)
while fast:
while fast.next and fast.val == fast.next.val:
fast = fast.next
if slow.next == fast:
slow, fast = slow.next, fast.next
else:
slow.next = fast.next
fast = slow.next

return dummy.next```

O(N)

O(1)

Translate »