141、142. 环形链表
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
注：不允许修改链表。
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
解题思路
方法一：直接遍历就完事了
使用一个Set，将每次遍历的结点都存放起来，如果遇到相同结点，则return true
方法二：使用快慢指针
1、我们新建两个结点，一个快指针，一个慢指针
2、当我们的慢指针走一步的时候，快指针走两步，那么，如果他们两者相遇的话，则该链表有环
注意：排除如果head直接为空或者next结点为空的情况，返回false
完整代码：
public class Solution {
public boolean hasCycle(ListNode head) {
if(head==null||head.next==null){
return false;
}
ListNode fast = head.next;
ListNode slow = head;
while(slow!=fast){
if(fast==null||fast.next==null){
return false;
}
fast= fast.next.next;
slow= slow.next;
}
return true;
}
}
进阶
返回这个环起始的结点
方法一： 同上，直接遍历，遇到相同的结点则直接拿出来返回即可
该方法时间复杂度O(N)，空间复杂度O(N)
完整代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head==null||head.next==null){
return null;
}
Set<ListNode> set = new HashSet<ListNode>();
while(head.next!=null){
if(!set.add(head)){
return head;
}
head=head.next;
}
return null;
}
}
方法二： 同样使用快慢指针
1、我们需要先探讨下其中的数学关系。
2、假设，出发点到环的入口距离为a，相遇的位置距离路口为b，环中往后剩下的距离为c
3、那么，在他们相遇的时候，假设，快指针在环内走了n圈，这时候他走的总距离为a+(b+c)n+b，化简得a+(n+1)b+cn
4、慢指针此时能走的路径为a+b，为什么慢指针一定在第一圈被追上呢：
- 第一步：设当n进入环的时候，快指针距离慢指针x的距离，环的长度为n
- 第二步：我们知道，快指针的速度为2，慢指针速度为1，所以想要追上的话，需要n-x的时间
- 第三步：只有n-x时间的话，慢指针是根本走不了一圈环的，所以，慢指针一定在第一圈内被追上
5、又有，快指针是慢指针的两倍，所以有a+(n+1)b+cn=2(a+b)，化简后即为a=c+(n?1)(b+c)，由此我们会发现：从相遇点到入环点的距离加上 n-1 圈的环长，恰好等于从链表头部到入环点的距离，即a里面有很多个环的距离，一起减掉这些后，相遇的位置是不会变的，剩下一起往后走个c距离即可
6、所以，在他们相遇的时候，我们仅需另起一个新的指针从头结点开始，每当慢指针往后移动一个结点，新指针也移动一次，当他们相遇的时候，该结点即为环的起始位置
完整代码
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode slow = head, fast = head;
while (fast != null) {
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return null;
}
if (fast == slow) {
ListNode ptr = head;
while (ptr != slow) {
ptr = ptr.next;
slow = slow.next;
}
return ptr;
}
}
return null;
}
}