常见算法技巧之——双指针思想
双指针思想是指设置两个指针解决一些算法问题。一般用的比较多的就是去解决数组、链表类的问题，还有很耳熟能详的二分查找问题。本文将根据自己平时做题的总结以及在网上看到的其他大佬的总结讲解来讨论一下双指针的使用技巧。本文会根据我平时做题实时更新。
快慢指针 双指针的快慢指针用法是我最开始理解的第一种用法。快慢指针一般用来解决链表的问题多一些。设置一快一慢两个指针fast和slow，初始化指向链表表头。
1、计算链表的中点 给定一个链表，要求返回该链表的中点节点。
设置两个快慢指针，都从头节点开始，快指针每次前进两个节点，慢指针每次前进一个节点，当快指针到达链表末尾的时候，慢指针刚好到达中点的节点。
下图中蓝色指针表示快指针，橙色指针表示慢指针。
如果已知一个单链表的表头，判断该链表中是否含有一个环。通常单链表都是一个节点只指向下一个节点这样的链式结构，如果只有一个指针，从头节点开始一路next，如果碰到null则表示有环，但如果没有环则会一直在环里打转，所以单指针很难解决这样的问题。
设置双指针，两个指针一快一慢，按照不同的速度从头节点开始往下遍历，如果最后两个指针相遇则表示有环，如果没有相遇，而是快指针先到了null则表示没有环。
public boolean hasCycle (LinkedList head) { LinkedList fast = head; LinkedList slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { //最后两指针相遇，表示有环 return true; } } return false; //若两指针不相等，则说明快指针到了null } 3、如果链表中有环，返回环的起始位置 如果已知一个链表中含有环，要找出环的位置，返回环的起始节点。
按照2中所说两个指针相遇的时候说明这个链表中有环，那么既然快指针速度是慢指针速度的二倍，那么假设两个指针第一次相遇的时候慢指针走了k步，则快指针就走了2k步，那么快指针的路程减去慢指针的路程就是环的长度，即为k。
那此时假设环的起点距离两指针的相遇点的距离为m，则从开始相遇点继续往下走，直到再次达到环起点，一共走了k-m步，而之前假设慢指针走了k步，从开始到第一次相遇，慢指针是从链表表头到第一次相遇点，走了k步，那么慢指针从表头到环的起点位置的距离也应该是k-m步（因为环起点距离相遇点是m步）。因此当两指针第一次相遇的时候，将一个指针重新置到头节点，然后两个步调一致，同样速度，每次前进一步，当再次相遇的时候，相遇位置就是环的起点。
这个很简单，当两个指针第一次相遇的时候，保持快指针不动，让慢指针继续跑，两指针再次相遇的时候慢指针跑的距离就是环的长度。
5、求链表倒数第k个节点 先让某个指针走k步，然后两个指针同时走，当前面的指针走到末尾的时候，后面的指针呢恰好走到倒数第k个节点。
leetcode中的例题
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode fast = head; ListNode slow = head; while (k > 0) { --k; fast = fast.next; } while (fast!=null) { fast = fast.next; slow = slow.next; } return slow; } } 左右指针 也有叫做碰撞指针的，通常需要一个有序的数组，左右两个指针其实就是指示数组的下标，通常一个初始化在开头，一个初始化在结尾。
1、二分查找 这个是很经典的例子，在有序的数组中查找某个数（记为x），返回下标。