LeetCode_双指针法的题目实例

  双指针的含义是数组中的两个指针，也可以是数组的两个下标。
双指针一般有两种用法:
第一种是一个指针从头向后移动，另一个指针从尾部向前移动。
第二种是两个指针抖从头部向后移动，但是一个移动的快，一个移动的慢。

026_删除排序数组中的重复项

public class N26_删除排序数组的重复项 {

    public int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    } else {

        int index = 0;
        for (int i = 1; i < nums.length; i++) {
        if (nums[index] != nums[i]) {
            // 1.先判断nums[i]和nums[index]是否相等，若不等那么index加1，此时index=1,令nums[1]=nums[1]
            // 2.若相等则不处理，此时index=0,判断nums[i+1]和nums[index]是否相等，若不等重复第1步。
            // 以此类推，判断到最后一个元素
            index++;
            nums[index] = nums[i];
        }
        }
        return index + 1;
        // 一共更新了index个元素，再加上nums[0],因此数组一共有index+1个元素
    }
    }
}

运行结果：

027_移除元素

public class N27_移除元素 {

    public int removeElement(int[] nums, int val) {
    if (nums.length == 0) {
        return 0;
    } else {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
    // 1.先判断nums[i]和val是否相等，若不等那么令nums[index]=nums[i],index加1，此时index=1
    // 2.若相等则不处理，此时index=0,判断nums[i+1]和val是否相等，若不等重复第1步。
    // 以此类推，判断到最后一个元素
            nums[index] = nums[i];
            index++;
        }
        }
        return index;
    // 遍历整个数组之后，index为不等于val的元素的数量，也就是处理后的数组的长度
    }
    }
}

运行结果：

083_删除排序链表中的排序元素

public class N83_删除排序链表中的排序元素 {

    public ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode res = head;
        while (head != null && head.next != null) {
            //相等的话就删除下一个节点
            if (head.val == head.next.val) {
                head.next = head.next.next;
            } else {
                //不相等的话向前移动一位
                head = head.next;
            }
        }
        return res;
    }


    //递归写法
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            //如果值和下一个值相同，删掉这个节点，即直接返回下一个节点
            return deleteDuplicates(head.next);
        } else {
            head.next = deleteDuplicates(head.next);
        }
        return head;

    }
}

运行结果：

283_移动零

public class n283_移动零 {
    public void moveZeroes(int[] nums) {

        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
     // 1.先判断nums[i]是否为0，若不等为0那么令nums[index]=nums[i],index加1，此时index=1,
     // 2.若为0则不处理，此时index=0,判断nums[i+1]是否为0，若不为0重复第1步。
     // 以此类推，判断到最后一个元素
            nums[index] = nums[i];
            index++;
            }
        }
       // 前面index个元素已经筛选出数组中所有不为0的元素，剩下nums.length — index个元素都为0
        for (int j = index; j < nums.length; j++) {
            nums[j] = 0;
        }

        }
    }

运行结果：