如何删除单个链表中的循环?

3 algorithm

我不确定如何在不使用O(N)内存和标志的情况下找到循环的开始

yai*_*chu 6

  • 在循环中查找节点(有关详细信息,请参阅1800 INFORMATION的答案).我们称这个节点为C
  • 通过从C推进指针直到它再次到达C来查找循环的长度.循环的长度是它所采取的步骤数.我们称这个长度为L.
  • 创建一个从起始点开始向前迈步的指针,以及指向开始的另一个指针.现在一步一步推进他们,直到他们相遇.这将是循环的切入点.

O(N)时间,O(1)记忆.

顺便问一下,你需要这个吗?