算法中快慢指针的应用(Java)
何为快慢指针？快慢指针就是指两个指针在移动的过程中，慢的指针每次移动一步，而快的指针每次移动两步。
快慢指针的应用一 (判断一个链表是否有环)：
问题来源：leetcode-141题，环形链表 https://leetcode-cn.com/problems/linked-list-cycle/
解法一：在这道题中，我首先想到的办法也是哈希表。遍历所有的结点，并在哈希表中存储每个结点的引用。若当前结点为空结点，则返回null，表示该单链表中没有环。若发现当前结点已经存在于哈希表中，则返回true。这种方法的时间复杂度和空间复杂度均为O(n)。
解法二：快慢指针法，想像两个长跑运动员在赛跑，若跑道中存在环，则快的长跑员一定会追上慢的长跑员。因此，使用两个指针，一个fast，一个slow，判断条件即为当 fast == slow时，返回true，表示有环。否则，当fast == null时，则返回null，此时快指针已经为null，表示不存在环。该方法的时间复杂度为O(n),空间复杂度为O(1)。
public static boolean hasCycle(ListNode head) {
ListNode slow = head;
if(slow == null) return false;
ListNode fast = head.next;
while(fast != null && fast.next != null){
if(slow == fast) return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}快慢指针的应用二 (找到有环链表的切入结点)：
问题来源：leetcode-142 环形链表二 https://leetcode-cn.com/problems/linked-list-cycle-ii/
双指针解题思路：慢指针和快指针同时从头结点head出发，移动过程中，若快指针为null，则返回null，表示当前链表中不存在环。 否则，当快指针等于慢指针时，即slow == fast时，此时，让头指针head和慢指针slow同时开始移动，每次移动一步，直到头指针head和慢指针slow相等时，返回当前头指针即为切入结点。图示为什么是这样：
将链表抽象为一条跑道，假设切入结点距离头指针head的距离为a，slow和fast相遇的结点处距离头指针head的距离为a + b。当慢指针和快指针相遇的时刻，slow走过的距离即为a + b，快指针移动的距离为慢指针的两倍，因此快指针移动的距离为2a + 2b。
此时，让慢指针slow和头指针head同时移动，当slow和head相等时，则此时慢指针一共移动的距离为2a + b。从开始的分析可知，slow == fast的那个点为fast走过2a + 2b，因此，2a + b的结点位置即为 切入结点所在的位置。
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
boolean ifhas = false;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
if(fast == slow) {
ifhas = true;
break;
}
}
if(!ifhas) return null;
while(head != slow) {
head = head.next;
slow = slow.next;
}
return head;
}快慢指针的应用三 (寻找链表的中间结点)：
问题来源：leetcode-148 有序链表 https://leetcode-cn.com/problems/sort-list/
并不是题目要求寻找链表的中间结点，只是想到要在O(n log n)的时间复杂度下对链表进行排序，自然想到归并算法。但是归并算法要将链表一分为二，在这里就要用到快慢指针法。
快慢指针在这里的应用思路很清晰，快慢指针同时从head出发，慢指针slow每次移动一步，快指针fast每次移动两步，当快指针为null时，慢指针也就达到了链表的中间位置。接下来就直接使用归并算法进行排序了。