#定义

双指针，通常指的是在遍历数组对象时，使用两个指针进行扫描。根据指针前进的方向不同分为快慢指针（方向相同）和对撞指针（方向相反）。双指针利用了数组索引有序的特征从而简化某些情况下的处理。

#对撞指针

对撞指针是指在有序数组中，将指向最左侧的索引定义为左指针，最右侧的索引定义为右指针，然后从两头向中间遍历。对撞指针适用于有序数组，可以考虑使用对撞指针来处理有序数组相关问题。
伪代码大致如下：

  1. public void func(list) {
  2.     int left = 0;
  3.     int right = N - 1;
  5.     while (left <= right) {
  6.         left++;
  7.         .....
  8.         right--;
  9.     }
  10. }

#快慢指针

快慢指针也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，一般快指针移动2，慢指针移动1，当两个指针的值相等（或其他特殊条件）移动停止。
伪代码大致如下：

  1. public void func(Node node) {
  2.     Node slow = node;
  3.     Node fast = node;
  5.     while (slow.value != fast.value) {
  6.         slow = slow.next;
  7.         fast = fast.next.next;
  8.     }
  9.     return slow;
  10. }

#快慢指针的应用

#26 数组元素去重

  1. public int removeDuplicates(int[] nums) {
  2.     if (nums.length == 0) return 0;
  3.     int i = 0;
  4.     for (int j = 1; j < nums.length; j++) {
  5.         // nums[i]和nums[j]不相等时，i指针才会向前移动，且a[i...j-1]的元素都是相等的
  6.         if (nums[j] != nums[i]) {
  7.             i++;
  8.             nums[i] = nums[j];
  9.         }
  10.     }
  11.     return i + 1;
  12. }

#141 环形链表

  1. public boolean hasCycle(ListNode head) {
  2.     if (head == null && head.next == null) return false;
  4.     ListNode slow = head;
  5.     ListNode fast = head;
  7.     while (slow != fast) {
  8.         slow = slow.next;
  9.         fast = fast.next.next;
  10.     }
  12.     return slow;
  13. }

#142 环形列表2

  1. public ListNode func(ListNode head) {
  2.     ListNode slow = head;
  3.     ListNode fast = head;
  5.     while (slow != fast) {
  6.         slow = slow.next;
  7.         fast = fast.next.next;
  8.         if (slow == fast) {
  9.             ListNode index1 = slow;
  10.             ListNode index2 = head;
  11.             while (index1 != index2) {
  12.                 index1 = index1.next;
  13.                 index2 = index2.next;
  14.             }
  15.             return index1;
  16.         }
  17.     }
  18.     return null;
  19. }

#160 相交链表

  1. public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  2.     if (headA == null || headB == null) return null;
  4.     ListNode Pa = headA;
  5.     ListNode Pb = headB;
  7.     while (Pa != Pb) {
  8.         Pa = Pa == null ? headB : Pa.next;
  9.         Pb = Pb == null ? headA : Pb.next;
  10.     }
  12.     return Pa;
  13. }

#链表二分

  1. public ListNode EndOfFirstHalf(ListNode head) {
  3.     ListNode slow = head;
  4.     LsitNode fast = head;
  6.     while (fast.next != null && fast.next.next != null) {
  7.         slow = slow.next;
  8.         fast = fast.next.next;
  9.     }
  10.     return slow;
  11. }

# 参考

  1. 对撞指针——常用题型
  2. 算法一招鲜——双指针问题
  3. 数据结构和算法-双指针法