In the Leetcode Remove Duplicates from Sorted List II problem 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.
Example 1:
Input: head = [1,2,3,3,4,4,5]
Output: [1,2,5]
Example 2:
Input: head = [1,1,1,2,3]
Output: [2,3]
Constraints:
- The number of nodes in the list is in the range [0, 300].
- -100 <= Node.val <= 100
- The list is guaranteed to be sorted in ascending order.
Solution in C Programming
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplicates(struct ListNode* head)
{
struct ListNode* before_head = malloc(sizeof(struct ListNode));
before_head->next = head;
struct ListNode* p1 = before_head;
struct ListNode* p2 = head;
while(p2!=NULL)
{
bool should_del = false;
while(p2->next!=NULL && p2->val == p2->next->val)
{
should_del = true;
p2 = p2->next;
}
if(should_del)
p1->next = p2->next;
else
p1 = p1->next;
p2 = p1->next;
}
return before_head->next;
}Solution in C++ Programming
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head || !head->next) return head;
auto run = head->next;
while(run && run->val == head->val) run = run->next;
if(run != head->next) return deleteDuplicates(run);
head->next = deleteDuplicates(run);
return head;
}
};Solution in Java Programming
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode p1 = new ListNode(-1);
ListNode cur = p1;
while (head != null) {
if (head.next != null && head.val == head.next.val) {
while (head.next != null && head.val == head.next.val) {
head = head.next;
}
head = head.next;
} else {
cur.next = head;
cur = cur.next;
head = head.next;
cur.next = null;
}
}
return p1.next;
}
}Solution in Python Programming
class Solution(object):
def deleteDuplicates(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
memo = collections.defaultdict(int)
while head:
memo[head.val] += 1
head = head.next
for key,value in memo.items():
if value > 1:
memo.pop(key)
dummy = ListNode(0)
res = dummy
for i in sorted(memo.keys()):
dummy.next = ListNode(i)
dummy = dummy.next
return res.next Solution in C# Programming
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode DeleteDuplicates(ListNode head) {
if(head==null || head.next==null) return head;
ListNode current = head;
ListNode PreHead = new ListNode(0);
ListNode finalCurrent = PreHead;
Dictionary<int, int> dict = new Dictionary<int, int>();
while (current != null)
{
if (dict.ContainsKey(current.val))
{
dict[current.val]++;
}
else
{
dict.Add(current.val, 1);
}
current = current.next;
}
foreach (var d in dict)
{
if (d.Value == 1)
{
finalCurrent.next = new ListNode(d.Key);
finalCurrent = finalCurrent.next;
}
}
return PreHead.next;
}
}Also read,