双指针使用 · Doublekai的博客

先来看一个简单的题目
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

class Solution {
    public void reverseString(char[] s) {
     /*
        定义两个指针一个指向头一个指向尾部
        两指针同时移动，将值交换。直到两指针重合或头大于尾则退出循环
        */
        int head=0,tail=s.length-1; //定义两个指针头、尾
        while (head<=tail){      //循环退出条件
            if(s[head] == s[tail]){  //如果相等则少一次交换
                head++;tail--;
                continue;
            }
            char temp=s[head];  //交换头尾值
            s[head++]=s[tail];
            s[tail--]=temp;
        }  
    }
}

接下来看一个双指针应用如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。如下图则True有环

而下面的则为False

方法一：直接将所有节点放在HashSet存储结构中遍历节点当该节点在表中存在则为True。
方法二：双指针利用快慢指针的思想，慢指针走得慢，快指针比慢指针快两倍，当快指针和慢指针相遇的时候则必有环为True代码如下：

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null ||head.next == null){
            return false;
        }
        ListNode after=head; //慢指针
        ListNode front=head.next;  //快指针
        while (after!=front){    //当快指针跟慢指针重合则跳出循环 返回True
            if (front == null ||front.next == null){   //如果快指针为空，说明不是环
                return false;
            }
            front=front.next.next;   //快指针移动要比慢指针快一步
            after=after.next;    慢指针正常移动
        }
        return true;
    }
}

双指针实现奇偶数排序
给定一个非负整数数组A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当A[i] 为奇数时，i也是奇数；当A[i]为偶数时， i 也是偶数。
分析：
方法一：重新定义一个数组B，遍历A当A[i]为奇数时放入奇数下标中j=1,j+=2,B[j]=A[i]，同理再次遍历A，将偶数放入B中
可以看出来时间复杂度为O（n），使用新的空间；
方法二：利用双指针
1.定义两个指针分别指向偶数下标和奇数下标
2.当偶数下标不是偶数时移动奇数下标指针当找到奇数下标不是奇数两个就可以交换
可能有点绕口接下来看A=[1,3,0,4] 当A[0]不是偶数时必定存在一个A[j]（j为奇数）不是奇数这里面也就是A[3],所以A[0]<=>A[3]交换则可以。

public int[] sortArrayByParityII(int[] nums) {
        /*
        给定一个非负整数数组A， A 中一半整数是奇数，一半整数是偶数。

        对数组进行排序，以便当A[i] 为奇数时，i也是奇数；当A[i]为偶数时， i 也是偶数。

        你可以返回任何满足上述条件的数组作为答案。
        1.定义两个指针分别指向偶数下标和奇数下标
        2.当偶数下标不是偶数时移动奇数下标指针当找到奇数下标不是奇数两个就可以交换
        */
        int odd=1;//奇数指针
        int enev=0;//偶数下标
        while (enev< nums.length){
            if(nums[enev]%2!=0){   //如果偶数下标是奇数的话，则找到奇数下标是偶数的交换则可以
                while (nums[odd]%2!=0){  // 找到奇数下标为偶数的值
                    odd+=2;
                    }
                int temp=nums[odd];   //交换
                nums[odd]=nums[enev];
                nums[enev]=temp;
            }
            enev+=2;
        }

        return nums;
    }

总结

在使用指针的过程中，要明白指针真正的含义，指针指向的不是值，而是值所待的地方也就是内存，当你明白这个道理那指针应用就会变得很简单，家都归你了何况家里的物品。