如何找到的链表是具有在它的周期的长度是多少？ [英] How to find the length of a linked list that is having cycles in it?

问题描述

这是问的面试问题之一。如何找到的链表是具有在其周期的长度。我知道如何计算一个链表是否有循环或不使用龟兔赛跑技术。我甚至知道如何通过存储地址HashSet的计算长度。该算法的运行时间应为O（n）。

This was one of the interview questions asked. How to find the length of a linked list that is having cycle in it. I know how to calculate whether a linked list has a cycle or not using Hare and Tortoise technique. I even know how to calculate the length by storing the addresses in a hashset. The running time of the Algorithm should be O(n).

但我不能告诉是如何计算链表的长度而不使用O（N）的外部空间。请帮我。谢谢你。

But what I was not able to tell is how to calculate the length of the linked list without using a external space of O(n). Please help me. Thank you.

推荐答案

我觉得如果有些你怎么知道周期的起始节点，就可以知道周期的长度和链表的节点，因此总数。

I think If some how you know the starting node of cycle , you can know the length of cycle and hence the total number of nodes in linked list.

有关获取出发点，你只需要O（1）空间。

For getting starting point you need only O(1) space.

假设你的两个指针，快和慢会见了在结点。

Suppose your two pointers,fast and slow met at 'node t'.

递增1指针指向下一个节点。 和其它指针开始的链表。 现在增加了两个三分球，直到他们满足。

increment one pointer to point to next node. and the other pointer to start of linked list. Now increment both the pointers until they meet.

本次会议点开始周期的节点。

The meeting point is starting node of cycle.

从这里就可以再次穿越，因为你知道周期的起点，获得周期的长度。

From this you can get the Length of cycle by traversing again since you know the starting point of cycle.

这篇关于如何找到的链表是具有在它的周期的长度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！