删除有序数组/链表中的重复元素

上例题

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

引入双指针思想，让慢指针 slow 走在后面，快指针 fast 走在前面，fast 找到一个不重复的元素就告诉 slow 并让 slow 接着走一步。这样当 fast 指针遍历完整个数组 nums 后，slow走过的数组元素就是删除重复元素后的数组元素。

上代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if(n == 0) return 0;
        int slow = 0, fast = 1;
        while(fast < n)
        {
            if(nums[fast] != nums[slow])
            {
                slow++;
                nums[slow] = nums[fast];
             }
             fast++;
        }
        return slow+1;
    }
};

同类型上例题

删除排序链表中的重复元素

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

输入：head = [1,1,2,3,3]
输出：[1,2,3]

上代码

/**
 * 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 == NULL) return NULL;
        ListNode *slow = head, *fast = head->next;
        while(fast != NULL)
        {
            if(fast->val != slow->val)
            {
                slow->next = fast;
                slow = slow->next;
            }
            fast = fast->next;
        }
        slow->next = NULL;
        return head;
    }
};