单向链表-链表有环判断

今天学习的算法是链表有环判断，这个题目的重点主要找到解题思路上面，下面让我们一起看看怎么实现吧。

题目介绍

给定一个链表，判断是否有环。我们用张图来表示下吧：

链表有环-题目.png

实现思路

老规矩，先看解题思路图。

链表有环-解题.png

难点说明

这个题目比较有名的算法就是使用快慢指针来实现了，基于快慢指针实现主要是理解为什么链表有环的情况下，两个指针一定会相遇。

首先，我们看下如果没有环时，只要在移动过程中发现快指针为null或者快指针的next为null就说明链表是没有环的。

接下来，我们看下若有环时，快慢指针时为什么会相遇吧。
1.如图所示，在慢指针进入环之前，两个指针是肯定不会相遇的。
2.当慢指针移动到环节点时，假设快指针与慢指针的距离为N。也就是类似慢指针在前面跑，每次跑一步，快指针在后面追，每次跑两步。
3.根据数学归纳法，在移动了m次后，快指针距离慢指针一定为0或1。因为没移动一次快指针距离慢指针的距离就减1。
4.若快慢指针距离为0说明节点相遇，若快慢指针距离为1那只要再移动一次就相遇了。
5.只要节点相遇了那就说明链表是有环的。

实现代码

public boolean hasCycle(ListNode head) {
    if (null == head || null == head.next) {
        return false;
    }
    ListNode stepOneNode = head;
    ListNode stepTwoNode = head;
    while (null != stepTwoNode && null != stepTwoNode.next) {
        stepOneNode = stepOneNode.next;
        stepTwoNode = stepTwoNode.next.next;
        if (null != stepTwoNode && stepOneNode.val == stepTwoNode.val) {
        return true;
        }
    }
    return false;
}

这个代码还是比较简介的。