双指针

由于之前学习过二分查找、滑动窗口的题目，不难看出，使用的方法本质上就是双指针。 这一篇中将学习另外两类技巧：

  1. 快慢指针：主要解决链表中的问题，如判定链表中是否包含环。
  2. 左右指针：主要解决数组（或字符串）中的问题，如二分查找。

快慢指针

快慢指针一般初始化都指向头节点，前进时快指针在前，慢指针在后。 下面通过一些应用题目来加深理解

  1. class Solutions {
  2.     /**
  3.      * 判定链表中是否含有环
  4.      * 遍历链表时通常采用此种方式，但遇到链表中含有环就会陷入死循环
  5.      * 经典解法使用两个指针指向链表，快慢指针
  6.      *      不含环的情况下，快指针优先遇到null
  7.      *      含有环的情况下，快指针最终会超过慢指针一圈，和慢指针相遇。
  8.      *      ？？这里是不是个物理问题，为什么快指针会超过慢指针一圈？
  9.      * @param head
  10.      * @return
  11.      */
  12.     boolean traverse(ListNode head) {
  13.         while (head != null) {
  14.             head = head.next;
  15.         }
  16.         return false;
  17.     }
  19.     boolean hasCycle(ListNode head) {
  20.         ListNode fast, slow;
  21.         fast = slow = head;
  22.         while (fast != null && fast.next != null) {
  23.             fast = fast.next.next;
  24.             slow = slow.next;
  25.             if (fast == slow) {
  26.                 return true;
  27.             }
  28.         }
  29.         return false;
  30.     }
  32.     /**
  33.      * 已知链表中含有环，返回环的起始位置
  34.      * @param head
  35.      * @return
  36.      */
  37.     ListNode detectCycle(ListNode head) {
  38.         ListNode fast, slow;
  39.         fast = slow = head;
  41.         while (fast != null && fast.next != null) {
  42.             fast = fast.next.next;
  43.             slow = slow.next;
  44.             if (fast == slow) break;
  45.         }
  46.         // 无论绕几圈，肯定能遇见
  47.         slow = head;
  48.         while (slow != fast) {
  49.             fast = fast.next;
  50.             slow = slow.next;
  51.         }
  52.         return slow;
  53.     }
  55.     /**
  56.      * 寻找链表中点
  57.      * 寻找中点的应用价值在于能够对链表做二分，能够实现二分链表则能够实现归并等操作
  58.      *
  59.      * @param head
  60.      * @return
  61.      */
  62.     ListNode middleNode(ListNode head) {
  63.         ListNode fast, slow;
  64.         fast = slow = head;
  65.         while (fast != null && fast.next != null) {
  66.             fast = fast.next.next;
  67.             slow = slow.next;
  68.         }
  69.         return slow;
  70.     }
  72.     /**
  73.      * 删除链表中倒数第N个节点
  74.      * @param head
  75.      * @param n
  76.      * @return
  77.      */
  78.     ListNode removeNthFromEnd(ListNode head, int n) {
  79.         ListNode fast, slow;
  80.         fast = slow = head;
  81.         while (n-- > 0) {
  82.             // 该题目中链表长度不超过n，未声明则需要判断
  83.             fast = fast.next;
  84.         }
  85.         if (fast == null) {
  86.             // 此时倒数第n个节点就是head，删除后即为null
  87.             return head.next;
  88.         }
  89.         while (fast != null && fast.next != null) {
  90.             fast = fast.next;
  91.             slow = slow.next;
  92.         }
  93.         // 删除第n个节点
  94.         slow.next = slow.next.next;
  95.         return head;
  96.     }
  97. }

左右指针

左右指针在数组中实际指两个索引值，一般 left = 0, right = nums.length - 1。 常用于二分查找等，下面是部分应用场景示例。

  1. class Solutions {
  2.     /**
  3.      * 二分查找是否有等于目标值的
  4.      * @param nums
  5.      * @param target
  6.      * @return
  7.      */
  8.     int binarySearch(int[] nums, int target) {
  9.         int left = 0, right = nums.length - 1;
  10.         while (left <= right) {
  11.             int mid = left + (right - left) / 2;
  12.             if (nums[mid] == target) {
  13.                 return mid;
  14.             } else if (nums[mid] < target) {
  15.                 left = mid + 1;
  16.             } else {
  17.                 right = mid - 1;
  18.             }
  19.         }
  20.         return -1;
  21.     }
  23.     /**
  24.      * 两数之和
  25.      * @param nums
  26.      * @param target
  27.      * @return
  28.      */
  29.     int[] twoSum(int[] nums, int target) {
  30.         int left = 0, right = nums.length - 1;
  31.         while (left < right) {
  32.             int sum = nums[left] + nums[right];
  33.             if (sum == target) {
  34.                 return new int[]{left + right};
  35.             } else if (sum < target) {
  36.                 left = left + 1;
  37.             } else {
  38.                 right = right - 1;
  39.             }
  40.         }
  41.         return new int[]{-1, -1};
  42.     }
  44.     /**
  45.      * 反转数组
  46.      * @param arr
  47.      */
  48.     void reverseString(char[] arr) {
  49.         int left = 0, right = arr.length - 1;
  50.         while (left <= right) {
  51.             char temp = arr[left];
  52.             arr[left] = arr[right];
  53.             arr[right] = temp;
  54.             left++;
  55.             right--;
  56.         }
  57.     }
  59.     // 最后一部分应用是滑动窗口，这部分不再重复，滑动窗口算是双指针高阶用法了，需要运用熟练。
  60. }