xiedaxia1hao
commented
3 years ago 快慢指针 & 链表有无环
leetcode 141. 环形链表即可以使用快慢指针解决。
给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 如果链表中存在环，则返回 true 。 否则，返回 false 。
从题意可知，需要对输入的链表判断其是否成环。初始化一个慢指针 slow，再初始化一个快指针 fast，fast 每次移动的速度比 slow 快一倍。如果快慢指针相遇，则判断有环。如果没有环，快慢指针不会相遇，并且快指针最终会走完链表。具体代码如下：
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
return true;
}
}
return false;
}
}fast 指针每次比 slow 多快一步。如果链表有环，那么 slow 和 fast 最终都会进入到环。
- 假设 fast 正好等于 slow，直接返回。
- 如果 fast 落后 slow 一步，那么下一次循环，slow 移动一步，fast 移动两步，fast 正好追上 slow，可以返回。
- 如果 fast 落后 slow 两步，那么下一次循环，slow 移动一步，fast 移动两步，fast 落后 slow 一步，可以归结为上一种情况，最终会相遇。
算法的最终时间复杂度为 O(n)，毕竟 slow 指针是一步步的迭代整个链表。空间复杂度为常数。
环形链表环的长度
这题可以有个很快速的followup，如果我们知道该链表有环，那么该环的长度该如何解呢？
实际上，有了环的入口，再通过环走一圈记录长度即可。那么可以再仔细想想，只要 slow 进入了环，那么起点不用从环的入口开始，当前位置作为起点，再走回当前位置即可。
public static int findCycleLength(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (slow == fast) // found the cycle
return calculateLength(slow);
}
return 0;
}
private static int calculateLength(ListNode slow) {
ListNode current = slow;
int cycleLength = 0;
do {
current = current.next;
cycleLength++;
} while (current != slow);
return cycleLength;
}环形链表的入口
使用快慢指针，不仅能判断链表是否有环，还能判断链表的环的起始位置。Leetcode 上的 142. Linked List Cycle II 是上一题的升级版。
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。 说明：不允许修改给定的链表。 进阶：你是否可以使用 O(1) 空间解决此题？
这题我们只需要记住，一旦 slow 和 fast 相遇，就让 slow 从新回到起点，fast 起始位置不变，但是步长变成和 slow 一样，当他们再次相遇，就是环的入口点。
那具体该如何证明呢？
如图，我们可以假设从起点到环入口的距离是m，环的长度为n，环的入口到fast和slow相遇的距离是y，剩下的距离是x。
根据fast走过的路程是2倍慢指针走过的路程，我们最终可以得到：
m = C * n + x，其中C是一个任意的常数。
通过这个式子，我们知道了，如果我们把slow指针移到最开始，fast的起始位置不变，但是每次和slow一样只走一个单位，那么当slow指针走了m长度的时候，fast刚好也走了x，这样这个式子只剩下了最后的C * n，代表着环的入口了。
所以我们的代码可以这么写：
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// find the cycle
if(fast == slow) {
slow = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}
}
141. 环形链表 142. Linked List Cycle II 234. 回文链表 143. 重排链表 202. Happy Number 457. 环形数组循环 189. 旋转数组 61. 旋转链表 80. Remove Duplicates from Sorted Array II 26. Remove Duplicates from Sorted Array
龟兔赛跑
相信很多人小时候听得最多的两个故事，莫过于高斯和龟兔赛跑了。高斯的故事让小朋友知道了学好数学的重要性，龟兔赛跑则无时无刻提醒小朋友们不要像兔子骄傲懈怠，同时也要像乌龟一样坚持不懈。
是的，学习算法技巧亦是。需要不断地练习，总结，持之以恒。然而，龟兔赛跑也是一个重要的算法技巧。也称之为 Floyd判圈算法。其主要目的是判断有限状态机、迭代函数或者链表是否有环。采用的技巧即使快慢指针，一个快，一个慢，正像兔子和乌龟一样，如果存在环，那么最终慢指针会遇到快指针。
证明就不具体描述，在头脑试想一下。假设一个跑道（链表）有环，那么无论兔子还是乌龟，总有一天它们都得进入跑道。并且进去之后就再也无法出来。那么一个快一个慢，快的就会逐渐超过慢的，最终会相遇。如果没有环，兔子又不懈怠，无论如何，慢的追不上快的，快的也不会遇见慢的。