一、快慢指针的常见算法

快慢指针一般都初始化指向链表的头结点head，前进时快指针fast在前，慢指针slow在后，巧妙解决一些链表中的问题。

1. 判断环

  1. boolean hasCycle(ListNode head) {
  2.     while (head != null)
  3.         head = head.next;
  4.     return false;
  5. }

但是如果链表中含有环，那么这个指针就会陷入死循环，因为环形数组中没有null指针作为尾部节点。

经典解法就是用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到null，说明链表不含环；如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。

  1. boolean hasCycle(ListNode head) {
  2.     ListNode fast, slow;
  3.     fast = slow = head;
  4.     while (fast != null && fast.next != null) {
  5.         fast = fast.next.next;
  6.         slow = slow.next;
  8.         if (fast == slow) return true;
  9.     }
  10.     return false;
  11. }

2. 寻找链表的中点.

快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。
力扣第 876 题就是找链表中点的题目，解法代码如下：

  2. ListNode middleNode(ListNode head) {
  3.     ListNode fast, slow;
  4.     fast = slow = head;
  5.     while (fast != null && fast.next != null) {
  6.         fast = fast.next.next;
  7.         slow = slow.next;
  8.     }
  9.     // slow 就在中间位置
  10.     return slow;
  11. }

二、左右指针的常用算法

左右指针在数组中实际是指两个索引值，一般初始化为left = 0, right = nums.length - 1。
1、二分查找
前文 二分查找框架详解 有详细讲解，这里只写最简单的二分算法，旨在突出它的双指针特性：

  1. int binarySearch(int[] nums, int target) {
  2.     int left = 0; 
  3.     int right = nums.length - 1;
  4.     while(left <= right) {
  5.         int mid = (right + left) / 2;
  6.         if(nums[mid] == target)
  7.             return mid; 
  8.         else if (nums[mid] < target)
  9.             left = mid + 1; 
  10.         else if (nums[mid] > target)
  11.             right = mid - 1;
  12.     }
  13.     return -1;
  14. }

2、两数之和
直接看力扣第 167 题「两数之和 II」吧：
[链表] 双指针问题 - 图1
只要数组有序，就应该想到双指针技巧。这道题的解法有点类似二分查找，通过调节left和right可以调整sum的大小：

  1. int[] twoSum(int[] nums, int target) {
  2.     int left = 0, right = nums.length - 1;
  3.     while (left < right) {
  4.         int sum = nums[left] + nums[right];
  5.         if (sum == target) {
  6.             // 题目要求的索引是从 1 开始的
  7.             return new int[]{left + 1, right + 1};
  8.         } else if (sum < target) {
  9.             left++; // 让 sum 大一点
  10.         } else if (sum > target) {
  11.             right--; // 让 sum 小一点
  12.         }
  13.     }
  14.     return new int[]{-1, -1};
  15. }

3、反转数组
一般编程语言都会提供reverse函数，其实非常简单，力扣第 344 题是类似的需求，让你反转一个char[]类型的字符数组，我们直接看代码吧：

  1. void reverseString(char[] arr) {
  2.     int left = 0;
  3.     int right = arr.length - 1;
  4.     while (left < right) {
  5.         // 交换 arr[left] 和 arr[right]
  6.         char temp = arr[left];
  7.         arr[left] = arr[right];
  8.         arr[right] = temp;
  9.         left++; right--;
  10.     }
  11. }

4、滑动窗口算法
这也许是双指针技巧的最高境界了，如果掌握了此算法，可以解决一大类子字符串匹配的问题，不过「滑动窗口」稍微比上述的这些算法复杂些。

更多