链表循环检测算法 [英] Linked list loop detection algorithm

问题描述

我在网上阅读了一些关于如何找到链表中是否存在循环的面试问题以及解决方案(Floyd's cycle-finding algorithm) 是有两个指针，一个比另一个快 2 倍，并检查它们是否再次相遇.

I read some interview question online about how would you find if there's a loop in a linked list, and solution (Floyd's cycle-finding algorithm) is to have two pointers, one is 2x faster than the other, and check if they meet again.

我的问题是:为什么我不能只保持一个指针固定，而是每次将另一个指针向前移动 1 步?

My question is: Why can't I just keep one pointer fixed, just move the other pointer forward by 1 step each time?

推荐答案

因为第一个(非移动)指针可能不在循环内，所以指针永远不会相遇.(请记住，循环可能只包含列表的一部分.)

Because the first (non-moving) pointer might not lie within the loop, so the pointers would never meet. (Remember that a loop may consist of only part of the list.)

这篇关于链表循环检测算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！