Floyd判圈算法
即龟兔赛跑算法
假想「乌龟」和「兔子」在链表上移动,「兔子」跑得快,「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时,如果该链表中没有环,那么「兔子」将一直处于「乌龟」的前方;如果该链表中有环,那么「兔子」会先于「乌龟」进入环,并且一直在环内移动。等到「乌龟」进入环时,由于「兔子」的速度快,它一定会在某个时刻与乌龟相遇,即套了「乌龟」若干圈。
力扣141.环形链表
给你一个链表的头节点head
,判断链表中是否有环。若链表中存在环,则返回true
,否则返回false
。
解:
定义快慢两个指针,慢指针每次移动一步,快指针每次移动两步。初始时,慢指针位于head处,快指针位于head->next处。在移动过程中,快指针追上满指针,则有环,否则快指针到达链表尾部,则无环。
1 | class Solution{ |
https://leetcode.cn/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution/