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]
Table of Contents
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);