LeetCode刷题：环形链表 与 环形链表II

1.环形链表

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例一：
示例二：

示例三：

1.哈希表求解

分析题目，这里可以采用哈希表求解，将ListNode作为HashSet集合中的元素存储起来，对链表进行一次遍历，如果当前链表节点不在集合中，则将当前的链表节点存入HashSet集合中，若遍历的链表节点在哈希表中，即表示当前链表存在环，返回true即可实现，具体代码如下：

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        Set<ListNode> set=new HashSet<ListNode>();
        while(head!=null){
    
            if(set.contains(head)){
    
                return true;
            }else{
    
                set.add(head);
                head=head.next;
            }
        }
        return false;
    }
}

2.时间复杂度分析

这里由于只有对链表的一次遍历，因此时间复杂度为$O(n)$，而空间由于用到了哈希表，因此空间复杂度也为$O(n)$，因为我们需要把遍历不在集合中节点元素添加到集合中！具体代码在LeetCode中的执行情况如下所示。可见执行效率不高，因此，我们就要寻找更加高效的方法！

3.快慢指针

由于前一种方法使用了哈希表，占用了空间复杂度，且算法执行效率不高，接下来我们用快慢指针来求解问题。
可以分别定义一个快指针fast，一次跳两个节点，一个慢指针slow，一次跳一个节点，使两个指针分别遍历链表，要知道，如果是环形链表，最后两个指针一定会相遇，即如果最后fast==slow,则表示该链表为环形链表，具体代码如下所示：

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public boolean hasCycle(ListNode head) {
    
        if(head==null) return false;
        ListNode fast=head,slow=head;
        while(slow!=null && fast.next!=null && fast.next.next!=null){
    
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow){
    
                return true;
            }
        }
        return false;
    }
}

4.GIF动图演示

如果对算法的实现思路还不能深刻理解，那么接下来看一下算法实现的动态过程吧，具体如下所示：

5.时间复杂度分析

按照快慢指针的方法，算法的时间复杂度仍然是$O(n)$，因为只有一次对链表的遍历，现在因为只定义了两个临时变量，与链表的规模无关，所以空间复杂度为$O(1)$。

2.环形链表II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例一：

示例二：

示例三：

1.快慢指针

这里的环形链表II是对环形链表的扩展，如果对环形链表理解了，那么这一题也十分简单。不过，这一题需要涉及到一定的数学证明。
我们使用两个指针，$\text{fast}$与 $\text{slow}$。它们起始都位于链表的头部。随后，$\text{slow}$指针每次向后移动一个位置，而 $\text{fast}$指针向后移动两个位置。如果链表中存在环，则 $\text{fast}$ 指针最终将再次与 $\text{slow}$指针在环中相遇。
如下图所示，设链表中环外部分的长度为 a。$\text{slow}$指针进入环后，又走了 b 的距离与 $\text{fast}$ 相遇。此时，$\text{fast}$指针已经走完了环的 $n$圈，因此它走过的总距离为 $a+n(b+c)+b=a+(n+1)b+nc$。
根据题意，任意时刻，$\text{fast}$指针走过的距离都为 $\text{slow}$指针的 2倍。因此，我们有
$a+(n+1)b+nc=2(a+b)*a=c+(n-1)(b+c)$
有了 $a=c+(n-1)(b+c)$的等量关系，我们会发现：从相遇点到入环点的距离加上 $n-1$圈的环长，恰好等于从链表头部到入环点的距离。
因此，当发现 $\text{slow}$与 $\text{fast}$相遇时，我们再额外使用一个指针 $\text{result}$。起始，它指向链表头部；随后，它和 $\text{slow}$每次向后移动一个位置。最终，它们会在入环点相遇。

按照上面的分析，现在我们只需要在环形链表的解题代码上添加一定的代码即可，即当fast==slow，即二者相遇判断环链存在时，重新定义一个从头结点开始的每次移动一个节点的指针，相遇后的slow节点也从相遇位置开始移动，由上述的数学证明，二者则一定会在环链开始的地方相遇！

/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */
public class Solution {
    
    public ListNode detectCycle(ListNode head) {
    
        if(head==null) return null;
        ListNode fast=head,slow=head;
        while(slow!=null && fast.next!=null && fast.next.next!=null){
    
            slow=slow.next;
            fast=fast.next.next;
            if(fast==slow){
    
                ListNode result=head;
                while(result!=slow){
    
                    result=result.next;
                    slow=slow.next;
                }
                return result;
            }
        }
        return null;
    }
}

2.时间复杂度分析

由于本次算法的实现包括判断是否为环链以及找到环链的初始位置，初始判断是否为环链时，$slow$慢指针的遍历节点数小于总结点数$N$，而接下来在环链的初始位置时，$result$指针也小于总结点数$N$，因此总的时间复杂度为$O(N)$
因为本次算法中只有简单变量，因此空间复杂度为$O(1)$。具体算法在LeetCode中的执行情况如下所示：