203题是在链表中删除一个固定的值，83题是在链表中删除重复的数值，但要保留一个；82也是删除重复的数值，但重复的都删除，不保留。
比如[1、2、2、3]，83题要求的结果是[1、2、3]，82题要求的结果是[1,3]。
这种题用递归去做比较方便思考，特别是这种重复的数值。递归就是只遍历当前的节点的情况，之前的不用管，之后的以当前节点为出发点思考问题。
203. Remove Linked List Elements
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(head == NULL)
return NULL;
if(head->val == val)
return removeElements(head->next,val);
else{
head->next = removeElements(head->next,val);
return head;
}
}
};
注意这种边界条件：
[1,1]
1
Expected:
[]
83. Remove Duplicates from Sorted List
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL)
return NULL;
int value = head->val;
while(head->next != NULL && head->next->val == value)
head->next = head->next->next;
head->next = deleteDuplicates(head->next);
return head;
}
};
82. Remove Duplicates from Sorted List II，这个题和剑指offer57 删除链表中重复的结点的题是一样的
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(head == NULL)
return NULL;
if(head->next == NULL)
return head;
if(head->val == head->next->val){
ListNode* node = head->next;
while(node != NULL && head->val == node->val)
node = node->next;
return deleteDuplicates(node);
}
else{
head->next = deleteDuplicates(head->next);
return head;
}
}
};
26、80两个题类似，第一个题是不允许有重复的数字，第二个题是允许每个数字最多重复两个，两个题目都要求在原数组上进行操作，并返回生成数组的长度，即空间复杂度为O(1)。
两个题都是使用双指针，第一个指针指向生成新的数组的最后一个位置，第二个指针指向当前进行判断的位置。
唯一不同的是， 第二个题需要设置一个变量来控制重复的个数是否超过2
26. Remove Duplicates from Sorted Array
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty())
return ;
int pre = ;
int cur = ;
while(cur < nums.size()){
if(nums[pre] == nums[cur])
cur++;
else
nums[++pre] = nums[cur++];
}
return pre + ;
}
};
80. Remove Duplicates from Sorted Array II
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty())
return ;
int pre = ;
int cur = ;
int count = ;
while(cur < nums.size()){
if(nums[pre] == nums[cur]){
if(count == )
cur++;
else{
nums[++pre] = nums[cur++];
count--;
}
}
else{
nums[++pre] = nums[cur++];
count = ;
}
}
return pre + ;
}
};
错误代码：
在这种情况下出错：{0,0,1,1,1,1,2,3,3};
这个代码用了多个if，多个if会重复计算，比如第一个if和第三个if会在同一次中重复计算。而我们想要的是每次计算一次。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(nums.empty())
return ;
int left = ,right = ,count = ;
while(right < nums.size()){
if(nums[left] == nums[right] && count != ){
nums[++left] = nums[right++];
count--;
}
if(nums[left] == nums[right] && count == )
right++;
if(nums[left] != nums[right]){
nums[++left] = nums[right++];
count = ;
}
}
return left + ;
}
};