这是悦乐书的第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<ListNode> nodesSeen = new HashSet<>();
while (head != null) {
if (nodesSeen.contains(head)) {
return true;
} else {
nodesSeen.add(head);
}
head = head.next;
}
return false;
}
此解法的空间复杂度是O(n)。
06 小结
笔试或者面试遇到此题时，推荐第一种解法，如果有限制链表节点值的取值范围，第二种解法也是完全可行的。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论