0

One question I came across, In a circular linked list, find node at the beginning of the loop?

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

Can one of the solutions be, to see if the address of value stored at these nodes are same?

So something like &(A->value) would return us address and then we find if an address is repeating, if yes that is the beginning of the loop?

Shubhendra Singh
  • 1
  • doesn't work if node stores by value (i.e. relies on copy semantics of the contained type). There are other ways to solve this problem... – Nim Oct 26 '11 at 15:06
  • It seems much easier to compare the nodes themselves, i.e. `A` instead of `&(A->value)`. (Although the latter will work too.) – avakar Oct 26 '11 at 15:07
  • You can numerate the nodes in the list with an incremental values. When traversing the list you can check if the value decrements (back at the begining) or incremrnts. – Marcin Oct 26 '11 at 15:08
  • In a common circular queue implementation using a linked list, two pointers are kept to point to the front and back nodes. This technique can be used to find the beginning and end of a circular linked list (if and only if designed this way). – Thomas Matthews Oct 26 '11 at 16:01

1 Answers1

3

You could do so, but this is very not efficient, in terms of space complexity, since you will need to store all nodes you 'saw along the way'.

A better solution would probably be Floyd's cycle finding algorithm, as described in this post

Community
  • 1
  • 1
amit
  • 175,853
  • 27
  • 231
  • 333
  • We already know the list is circular, so this is kind of overkill. – Jon Oct 26 '11 at 15:10
  • @Jon, what's the better alternative? Your answer doesn't say. – avakar Oct 26 '11 at 15:11
  • @avakar: I may have misunderstood the question. – Jon Oct 26 '11 at 15:12
  • @Jon: not really, the algorithm is extremely simple and has a low overhead, so it's not really a sledge-hammer. – Matthieu M. Oct 26 '11 at 15:13
  • @MatthieuM.: Well, either the q talks about a circular linked list in which we want to find "loops" based on duplicate node values rather than the links, or it talks about a graph (not a list) that contains a cycle -- confusing, so I don't even know if we have the same mental model here. – Jon Oct 26 '11 at 15:29
  • @amit: This looks fine for cyclic detection, but how to find the beginning of loop? – Shubhendra Singh Oct 26 '11 at 15:36
  • @ShubhendraSingh: You are right, and I misunderstood the question, Floyd's will allow you to find if there is a cycle. as my answer also mention, your solution will work as well, both to find if there is a cycle, and to find the exact first element in it. – amit Oct 26 '11 at 15:48