Remove Duplicates from Sorted List II LeetCode Solution

Table of Contents

Problem Statement

Remove Duplicates from Sorted List II LeetCode Solution – Given the head of a sorted linked list, delete 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:

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

Now, we traverse nodes and do the following steps:

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.
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.
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* deleteDuplicates(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        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 {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) return null;
        ListNode FakeHead=new ListNode(0);
        FakeHead.next=head;
        ListNode pre=FakeHead;
        ListNode cur=head;
        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;
        }
        return FakeHead.next;
    }
}

Python Code for Remove Duplicates from Sorted List II

class Solution:
    def deleteDuplicates(self, head):
        dummy = ListNode(-1)
        dummy.next = head
        fast, slow = head, dummy
        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