26-删除有序数组中的重复项.md

26-删除有序数组中的重复项

原题

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

const removeDuplicates = function (nums) {
    const n = nums.length;
    if (n === 0) {
        return 0;
    }
    let fast = 1, slow = 1;
    while (fast < n) {
        if (nums[fast] !== nums[fast - 1]) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

拓展：一个有序链表如何去重？

const removeDuplicates = function (head) {
    if (head === null) {
        return null;
    }
    
    let slow = head, fast = head.next;
    while (fast !== null) {
        if (fast.val != slow.val) {
            // 相等于 nums[slow] = nums[fast]
            slow.next = fast;
            // 相当于 slow++
            slow = slow.next;
        }
        
        // 相当于 fast++
        fast = fast.next;
    }
    
    // 断开与后面重复元素的连接
    slow.next = null;
    return head;
}