在一个单独的链表中寻找循环
我怎么能检测一个单独的链表是否有循环？ 如果它有循环，那么如何find循环的起始点，即循环已经开始的节点。
您可以通过简单地在列表中运行两个指针来检测它。
首先，如果列表为空（ head为null ），则不可能有循环，因此现在停止。 否则，如果列表只有一个元素（ head.next为null ），则不可能有循环，所以现在停下来。
否则，在第一个节点head开始第一个指针A ，在第二个节点head.next上开始第二个指针B
然后每次通过循环将指针A连续前进一个，并将指针B前进两个（如果元素用完，则前进一个）。
如果有一个循环，他们将最终指向同一个节点，你可以停下来，知道你已经find了一个循环内的节点。 如果没有循环，在B指针指向同一个节点之前，会用B指针结束。
考虑下面以3开始的循环：
head -> 1 -> 2 -> 3 -> 4 -> 5 ^ | | V 8 <- 7 <- 6
从1开始A，在2开始B，它们具有以下值：
(A,B) = (1,2) (2,4) (3,6) (4,8) (5,4) (6,6)
因为它们在(6,6)处是相等的，并且由于B在非循环列表中总是超出A （它开始于A之外并且移动得更快），这意味着你已经发现了一个循环。
伪代码将会像这样：
def hasLoop (pointer nodeA): # nodeA is first element of list. return false if nodeA == NULL # Empty list has no loop. nodeB = nodeA.next # Set nodeB to second element. while nodeB != NULL: # Go until B reaches end. nodeA = nodeA.next # Move A forward one. return false if nodeB.next == NULL # Check enough left for B move. nodeB = nodeB.next.next # Move B forward two. return true if nodeA == nodeB # Same means loop found. endwhile return false # Loop exit means no loop. enddef
一旦你知道循环内的一个节点，就有一个O(n)保证方法来find循环的开始 。
在循环中find某个元素后，回到原始位置，但不确定循环的起始位置。
head -> 1 -> 2 -> 3 -> 4 -> 5 ^ | | V 8 <- 7 <- 6 \ AB (where A and B first met).
这是要遵循的过程：
-
提前
B并将loopsize设置为1。 然后，当A和B不同时，继续前进B，每次增加loopsize。 这给出了循环的大小 ，在这种情况下是6。 -
如果在
B之后，loopsize为1，再次等于A，则意味着A.next等于A所以你知道你必须已经在循环的开始。 因此，您只需返回A作为开始，并跳过下面的其余步骤。 -
否则，将
A和B都设置为列表的第一个元素，并提前B完全loopsize次数（在这种情况下为7）。 这给出了两个指针，它们与循环的大小完全不同。 -
A和B不同，一起推进。 由于它们将始终保持完全loopsize分离的元素，因此A会在B返回到循环开始的同时正好到达循环的开始位置。
您可以看到，通过以下演练：
-
loopsize评估为6。 - 将
A和B都设置为1。 - 通过
loopsize元素提前B到7。 -
1和7不等于是都提前了。 -
2和8不等于是都提前了。 -
3和3是相等的，所以你的循环开始。
现在，由于每个操作都是O(n)并且按顺序执行，所以整个事情是O(n) 。
如果你想得到一个更正式的certificate，这可以检查以下资源：
- 我们姊妹网站上的一个问题 ;
- 维基百科周期检测页面; 要么
- Peter Gammie于2016年4月17日发表的“龟与兔子algorithm”
如果你只是简单的支持这个方法（而不是正式的certificate），你可以运行下面的Python 3程序来评估它对大量数据的可用性（循环中有多less个元素）和引入（在周期开始）。
你会发现它总能find两个指针相遇的地方：
def nextp(p, ld, sz): if p == ld + sz: return ld return p + 1 for size in range(1,1001): for lead in range(1001): p1 = 0 p2 = 0 while True: p1 = nextp(p1, lead, size) p2 = nextp(nextp(p2, lead, size), lead, size) if p1 == p2: print("sz = %d, ld = %d, found = %d" % (size, lead, p1)) break
选定的答案给出一个O（n * n）的解决scheme来find循环的开始节点。 这是一个O（n）解决scheme：
一旦我们发现慢速A和快速B在循环中相遇，使其中一个静止，另一个继续每次一步，以决定周期的周长，比如说P.
然后我们把一个节点放在头上，让它走P步，把另一个节点放在头上。 我们把这两个节点每次都推进一步，当他们第一次见面的时候，就是这个循环的起点。
你也可以使用哈希映射来查找链表是否有循环或下面的函数使用哈希映射来找出链表是否有循环
static bool isListHaveALoopUsingHashMap(Link *headLink) { map<Link*, int> tempMap; Link * temp; temp = headLink; while (temp->next != NULL) { if (tempMap.find(temp) == tempMap.end()) { tempMap[temp] = 1; } else { return 0; } temp = temp->next; } return 1; }
两个指针方法是最好的方法，因为时间复杂度是O（n）哈希映射需要增加O（n）空间复杂度。
下面的代码将会发现SLL中是否有循环，如果有的话，会返回起始节点。
int find_loop(Node *head){ Node * slow = head; Node * fast = head; Node * ptr1; Node * ptr2; int k =1, loop_found =0, i; if(!head) return -1; while(slow && fast && fast->next){ slow = slow->next; /*Moving fast pointer two steps at a time */ fast = fast->next->next; if(slow == fast){ loop_found = 1; break; } } if(loop_found){ /* We have detected a loop */ /*Let's count the number of nodes in this loop node */ ptr1 = fast; while(ptr1 && ptr1->next != slow){ ptr1 = ptr1->next; k++; } /* Now move the other pointer by K nodes */ ptr2 = head; ptr1 = head; for(i=0; i<k; i++){ ptr2 = ptr2->next; } /* Now if we move ptr1 and ptr2 with same speed they will meet at start of loop */ while(ptr1 != ptr2){ ptr1 = ptr1->next; ptr2 = ptr2->next; } return ptr1->data; }
boolean hasLoop(Node *head) { Node *current = head; Node *check = null; int firstPtr = 0; int secondPtr = 2; do { if (check == current) return true; if (firstPtr >= secondPtr){ check = current; firstPtr = 0; secondPtr= 2*secondPtr; } firstPtr ++; } while (current = current->next()); return false; }
另一个O（n）解决scheme。
一个完全不同的方法： – 反转链表。 如果您再次到达头部，则会反转，然后在列表中有一个循环，如果您获得NULL，则不会有循环。 总的时间复杂度是O（n）
当我看到选定的答案时，我尝试了几个例子，发现：
如果（A1，B1），（A2，B2）…（AN，BN）是指针A和B的遍历
其中A步骤1个步骤，B步骤步骤2个步骤，Ai和Bj是A和B所遍历的节点，AN = BN。
然后，循环开始的节点是Ak，其中k = floor（N / 2）。
好的 – 我在昨天的采访中遇到了这个问题 – 没有提供参考资料，我想出了一个非常不同的答案（当然是在开车回家的时候…）因为链接列表是正常的（并不总是我承认）使用malloc逻辑那么我们知道分配的粒度是已知的。 在大多数系统中，这是8个字节 – 这意味着底部3位总是零。 考虑一下，如果我们把链表放在一个类中来控制访问，并在下一个地址中使用一个0x0E的掩码，那么我们可以使用低三位来存储一个break crumb。因此，我们可以写一个方法来存储我们最后一个面包屑 – 说1或2 – 并交替。 我们检查循环的方法可以遍历每个节点（使用我们的下一个方法），并检查下一个地址是否包含当前的面包屑 – 如果有，我们有一个循环 – 如果没有，那么我们将屏蔽低3位并添加我们目前的面包屑。 面包屑检查algorithm必须是单线程的，因为你不能同时运行其中的两个，但它会允许其他线程访问列表asynchronous – 通常有关添加/删除节点的警告。 你怎么看？ 如果别人觉得这是一个有效的解决scheme，我可以写出样本class…只是觉得有时一个新的方法是好的，总是愿意被告知我刚刚错过了这一点…谢谢所有马克
