大家好,我是闭着眼睛学算法。
今天早上我在 LeetCode 第 141 号问题 环形链表 的评论区中发现了一个称得上是天秀的解法,简直太骚气了,忍不住分享给大家。
首先给没有见过这道题目的小伙伴补充一下前置知识, 环形链表这道题目讲的是给你一个链表的头节点 head ,判断链表中是否有环。
所谓链表有环,直观上来看就是这个样子:
严谨一些的说明指的是如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。
一般正经解法是使用快慢指针的思路,即在开头设置两个指针,一个跑的快,一个跑的慢,如果两个指针再次重新相遇,那么就说明有环。
这个思路挺好理解的,在一个环形操场上,跑的快的人总是能和跑的慢的人再次相遇。
但是这个评论区的小伙伴面向测试用例编程,给出了如下的代码:
public class Solution {
public boolean hasCycle(ListNode head) {
int count = 8029;
while( head != null && count > 0){
head = head.next;
count--;
}
if( head == null ) return false;
return true;
}
}
上述代码的含义是从链表的头节点,沿着链表不断地向后移动,移动 8029
次后,如果此时指向的是空,说明链表是一条直线不存在环,反之存在环。
很合理的思路!
如果一个链表的长度小于 8029
,当它没有环时,不需要移动 8029
次就会来到尾部指向 null
;当它存在环时,那么会在这个环中绕圈圈,最终移动 8029
次后指向一个存在值的节点。
提交一下代码,报错!
点击查看全部,发现最后一个测试用例链表的长度扩充到了 10000
。
简单的修改一下代码,将 count = 8029
修改为 count = 10001
,再次提交。
牛逼,击败 100% !
LeetCode 评论区的人才可真多!