Remove Duplicates From Sorted List II Problem Solution

Remove Duplicates From Sorted List II: 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]

Remove Duplicates From Sorted List II Problem Solution

Problem Solution In Python

class Solution(object):
    def deleteDuplicates(self, head):
        if not head or not head.next :
            return head
        p = head
        while p.next and p.val == p.next.val:
            p = p.next
        if p != head:
            head = p.next
            return self.deleteDuplicates(head)
        head.next = self.deleteDuplicates(head.next)
        return head

Problem Solution In Java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) return head;
        
        ListNode pre = new ListNode(-1, head);
        ListNode curr = head;
        ListNode dummyHead = pre;
        
        while (curr != null && curr.next != null) {
            if (curr.val == curr.next.val) {
                while (curr != null && curr.next != null && curr.val == curr.next.val) {
                    curr = curr.next;
                }
                pre.next = curr.next;
            } else {
                pre = curr;
            }
            curr = curr.next;
        }
        
        return dummyHead.next;
    }
}

Problem Solution In C++

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL) return head;
        ListNode *p0,*p1;
        p0 = new ListNode(0); /*It is convenient to create a node before head*/
        p0->next = head;
        p1 = p0;
        while(p1->next!=NULL){  /*remove the duplicates after and next to p1*/
            ListNode *tmp = p1->next;
            int current = tmp->val, count = 1;
            tmp = tmp->next;
            while(tmp != NULL && tmp->val == current){
                count++;
                tmp = tmp->next;
            }
            if(count > 1) p1->next = tmp;
            else p1 = p1->next;
        }
        return p0->next;
    }
};

Problem Solution In C

if(head == NULL)
    return NULL;
    
struct ListNode *p1,*p2;
p1 = head ; p2 = head;

while(p2 != NULL && p2->val == p1->val)
    p2 = p2->next;

if(p1->next == p2)
{
    p1->next = deleteDuplicates(p2);
    return p1;
}
else
    return deleteDuplicates(p2);

Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment