10

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).

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.

bragboy
  • 34,892
  • 30
  • 114
  • 171
  • What's the expected running time? – kennytm May 05 '10 at 12:14
  • 3
    If you need O(n) space to use hare and tortoise, you're doing something wrong. See for instance http://stackoverflow.com/questions/34249/best-algorithm-to-test-if-a-linked-list-has-a-cycle – Gabe May 05 '10 at 12:14
  • ...having "cycle" (singular) or "cycles" (plural)? That does make a difference. – sbi May 05 '10 at 12:24
  • 2
    He's using O(n) space to count the number of distinct nodes, not just to detect the cycle. – Steve Jessop May 05 '10 at 12:24
  • @sbi: Its singular. @Kenny: O(n). – bragboy May 05 '10 at 12:25
  • 2
    @sbi: how can a linked list have more than one cycle? If any node has more than one out-link it's not a linked list any more, it's a directed graph. – Steve Jessop May 05 '10 at 12:26
  • @Steve: That's why I wrote it's important. The title still reads "How to find the length of a linked list that is having cycles in it?", though. – sbi May 05 '10 at 13:00
  • That's what I like in the interview questions: the question is theoretically interesting but I would be hard pressed to find a usecase within a minute. Seriously, who manages linked list explicitly ? – Matthieu M. May 05 '10 at 13:07
  • 2
    @Matthieu: the techniques aren't only for linked lists, that's just a simple and familiar way to state the problem. They're also for finding cycles in PRNGs, or any other forward-only sequence you can think of. – Steve Jessop May 05 '10 at 13:26
  • The technique yes, and that's why I wonder why they don't state the problem with some real case issue rather than being all theoretic about it. It's like the interviewer picked up a Computer Science exercise book... wait, it may be the case after all :) – Matthieu M. May 05 '10 at 14:43
  • @Matthieu: Indeed, if the interviewer can think of a real use-case then it would be better to start with that, and only rephrase the question with a linked list if the candidate fails to make the connection. I strongly suspect that the purpose of this question is really just to confirm that the candidate actually remembers any computer-related education claimed in the CV ;-) – Steve Jessop May 05 '10 at 17:45

6 Answers6

24

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.

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

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

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.

Vikas
  • 1,422
  • 2
  • 12
  • 16
9

Once you've detected the cycle, you need to calculate the length of the cycle, and the position at which it starts. The sum of these is the total number of distinct nodes in the list. Details for example here: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • What said is true but finding it in O(n) without using O(n) space is a challenge. If you know the solution, please provide. – bragboy May 06 '10 at 16:50
  • @Bragadeesh: the method (and Python code) are in that Wikipedia article, and also in Vikas' answer. – Steve Jessop May 08 '10 at 00:50
4
  1. Apply Tortoise and Hare algorithm and stop when characters meet
  2. Continue iterating through the list only with Tortoise and reverse each link it will pass

The number of reversed links is the length of the cycle

Community
  • 1
  • 1
Vitalii Fedorenko
  • 110,878
  • 29
  • 149
  • 111
  • you can use snippets from this question http://stackoverflow.com/questions/494830/how-to-determine-if-a-linked-list-has-a-cycle-using-only-two-memory-locations – Vitalii Fedorenko Oct 04 '11 at 23:01
1

Detect loop point By (Slow pointer and fast pointer approach), find the loop detection node

Now take pointers P1 and P2, P1 at the loop detection node and P2 starting from head of the linked list Traverse both the pointers one at a time

Both the pointers meet at the node because of which there is a loop in the linked list

Use the standard fast and slow pointer algorithm find the loop detection point

Take two pointers P1 and P2 at loop detection point. Place pointer P1 at the same place and move P2 forward one step at a time. Repeat until both the pointers meet together. Keep a count variable incremented for every iteration which gives length of the loop. Let say the length is L1

Again take two pointers P1 and P2. P1 at the head of the linked list and P2 at the loop detection point. Forward both the pointers one step at a time. Repeat until both the pointers meet together. This procedure is equivalent to the one we use to calculate node that causes loop in a linked list. Keep a count variable incremented for every iteration which gives the length of the list until the merging point. Let say the length is L2 Now the length of the list that contains loop is L1+ L2

sa_nyc
  • 971
  • 1
  • 13
  • 23
1

Here's the mathematical justification of the correctness of the popular hare and tortoise algorithm for finding the length of the linked list.

Math of the hare and the tortoise

Community
  • 1
  • 1
gkb0986
  • 3,099
  • 1
  • 24
  • 22
0

wont it go in infinite loop? if 1 2 3 ... 9 10 form a loop ,which starts at 1.Suppose when pointer from start node reaches 1 ,other pointer is at node 8. then they move as pointer1:- 1 2 3 4 5 .. pointer2:- 8 9 10 1 2.. clearly they wont ever be equal.

sunny
  • 29
  • 3