使用快慢指针法判断链表是否有环,分别定义fast和slow指针从头结点出发,进循环,fast指针每次移动两个结点,slow指针每次移动一个结点,如果fast和slow在途中相遇(fast == slow),说明这个链表有环。循环结束说明链表没有环。
这里说明一下为什么fast和slow会在环中相遇而不是永远错开:
因为fast指针一定会先进入环中(如果有环存在的话),如果fast和slow相遇的话,一定是在环中相遇,这点是毋庸置疑的。
这里说明一下为什么fast和slow会在环中相遇而不是永远错开:
因为fast指针一定会先进入环中(如果有环存在的话),如果fast和slow相遇的话,一定是在环中相遇,这点是毋庸置疑的。
我已经通过这道算法题! 判断给定的链表中是否有环 扩展: 你能给出空间复杂度的解法么?
https://gw-c.nowcoder.com/api/sparta/jump/link?link=https%3A%2F%2Fwww.nowcoder.com%2FquestionTerminal%2F650474f313294468a4ded3ce0f7898b9
全部评论
相关推荐
点赞 评论 收藏
转发
04-20 18:13
合肥工业大学 计算机类 点赞 评论 收藏
转发