什么是解决循环链表的方法吗？ [英] what is the approach to solve circular linked list?

问题描述

给定一个循环链表，impplement的算法在循环的开始返回节点

Given a circular linked list, impplement an algorithm which returns node at the beginning of the loop.

定义： Cicular链接列表：A（损坏）链接的列表，其中一个节点的下一个指针指向一个较早的节点，从而使在该链接的表的循环

DEFINITION: Cicular Link list: A(corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.

例： 输入：A-> B-> C-> D-> E-> C [相同的C正如前面] 输出：C

EXAMPLE: Input: A->B->C->D->E->C[the same C as earlier] Output: C

推荐答案

您可以使用龟兔赛跑algortihm

1. 在开始用两个指针，调用一个龟和其他野兔
2. 在每一步，提前乌龟一次，兔子两次
3. 在重复，直到它们相等

1. Start with two pointers, call one the tortoise and the other the hare
2. At each time step, advance the tortoise once, and the hare twice
3. Repeat until they are equal

这让你在循环中的一个元素。为了找到循环的开始：

This gives you an element inside the loop. To find the beginning of the loop:

1. 推进乌龟一步一个脚印的时间，计算步数
2. 停止，直到你到达野兔

这将让你找到环路的长度。然后，你只需要一步尺寸长度次找到启动，其中尺寸中元素的个数您链接表。

This will allow you to find the length of the loop. Then you simply need to step size-length times to find the start, where size is the number of elements in your "linked-list".

这也被称为弗洛伊德的周期检测算法。

This is also known as Floyd's cycle detection algorithm.

这篇关于什么是解决循环链表的方法吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！