Linked List Cycle 判断单链表中是否有环

发布网友发布时间：2024-01-22 11:43

共1个回答

热心网友时间：2024-03-14 23:10

判断方法：
1、从链表头开始遍历整个链表，并且记录已经遍历过的结点地址，如果发现有正在遍历的结点是已经遍历过的，则说明是存在环的。但是这种方式就需要使用额外的空间来存放遍历过的结点地址。
2、设置两个指针，p和q，p从链表头开始，每次向前走一步，而q每次都从链表头开始，走到p会到达的结点，若p的累计步数和q每次的步数都一致，那么就不存在环，反之，则存在环。
3、设置两个指针，快指针p和慢指针q，两个指针都从链表头开始，p每次向前走两步，q每次向前走1步，若p始终在q的前面直到到达链表尾，那么就不存在环，若p和q在某一个结点相遇，那么说明存在环。