83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Approach : The key to solve the problem is using the right loop condition and maintaining necessary pointers in each loop.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* deleteDuplicates(struct ListNode* head) { struct ListNode *cur, *_next; if(head == NULL || head->next == NULL){ return head; } cur = head; while(cur && cur->next){ //set the pointer of the current next to the next node if duplicate is found if(cur->val == cur->next->val){ _next = cur->next->next; free(cur->next); cur->next = _next; }else{ //else just move forward to next node cur = cur->next; } } return head; }

Read More

Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if(head == NULL || head->next == NULL){ return head; } //create a dummy node to avoid the case of head value getting repeated which is difficult to handle struct ListNode *res = new struct ListNode(0); res->next = head; struct ListNode *cur = res; while(cur->next && cur->next->next){ //if the next value is same as its next value if(cur->next->val == cur->next->next->val){ int val = cur->next->val; //move forward if same value is repeating while(cur->next && cur->next->val == val){ cur->next = cur->next->next; } }else{ cur = cur->next; } } //return next of the dummy node return res->next; } };

Read More

Remove Duplicates from Sorted Array II

Modification of the problem "Remove Duplicates":
What if the duplicates are allowed at most twice in the resulting array?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

int Solution::removeDuplicates(vector<int> &nums) { if(nums.size() == 0){ return 0; } int count = 1; int j = 1; for(int i = 1 ; i < nums.size(); i++){ if(nums[i] != nums[i - 1]){ nums[j] = nums[i]; count = 1; j++; } else if(count == 1){ nums[j] = nums[i]; count = 2; j++; } } return j; }

Read More