这是悦乐书的第176次更新，第178篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第35题（顺位题号是141）。给定一个链表，确定它是否有一个循环。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 理解题意

什么样结构的链表才算是拥有一个循环呢？

链表中某一节点的引用指向了当前链表中已经存在的另一节点时，此链表存在循环。

ListNode L = new ListNode(1);ListNode L2 = new ListNode(2);ListNode L3 = new ListNode(3);ListNode L4 = new ListNode(4);ListNode L5 = new ListNode(5);ListNode L6 = new ListNode(6);L.next = L2;L2.next = L3;L3.next = L4;L4.next = L5;L5.next = L3;

上面的链表就存在循环，L5的引用指向了L3。如果仅仅是节点值相等，是不存在循环的，因为他们的引用始终不同。

03 第一种解法

可以打个比方，如果两个人甲和乙同时在一条跑道上跑步，甲以2.5m/s的速度向前跑，乙以5m/s的速度向前跑，如果跑道是环形的，甲和乙肯定会在某一个地方至少相遇一次；如果跑道是直线形或非环形的，甲和乙是不会相遇的。

使用双指针，一个是正常向前，一次移动一个节点，第二个是间隔一个节点向前移动，如果第二个指针碰到了可以循环的节点，会在循环的过程中遇到第一个指针，此时就满足了形成循环的条件。

特殊情况：链表为空时，直接返回false。

public boolean hasCycle(ListNode head) {    if (head == null) {         return false;    }    ListNode slow = head;    ListNode fast = head;    while (slow != null && fast != null && fast.next != null) {        slow = slow.next;        fast = fast.next.next;        if (slow == fast) {            return true;        }    }    return false;}

04 第二种解法

还是以上面跑步为例，不过稍微有点变化。甲还是以2.5m/s的速度跑步，此时乙在跑道中给了甲一根棒子，并站在原地等甲把棒子还给自己，如果跑道是环形的，乙肯定是会等到甲把棒子还给自己，如果跑道是直线或者非环形的，甲就带着棒子自己跑了。

我们可以使用一个标记，赋值给每一个节点，然后使用递归，直到碰到给出去的标志为止。

public boolean hasCycle2(ListNode head) {    if(head == null) {        return false;    }    if (head.val == Integer.MIN_VALUE-1) {        return true;    }    head.val = Integer.MIN_VALUE-1;    return hasCycle2(head.next);}

如果某一个节点正好本身就拥有所要赋值的标志呢？会有一定影响，如果限制节点值的取值范围，此解法是完全可行的。

05 第三种解法

使用哈希表，将每一个节点的引用都存起来，如果哈希表中存在了某一个节点的引用，说明此链表是循环的。

public boolean hasCycle3(ListNode head) {    Set
    
      nodesSeen = new HashSet<>();    while (head != null) {        if (nodesSeen.contains(head)) {            return true;        } else {            nodesSeen.add(head);        }        head = head.next;    }    return false;}
    

此解法的空间复杂度是O(n)。

06 小结

笔试或者面试遇到此题时，推荐第一种解法，如果有限制链表节点值的取值范围，第二种解法也是完全可行的。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！