Linked list

Question

What should be the basic approach or algorithm to find whether a linked list is circular or not?

Answer 1

This is probably the silliest method, but it should work:

1. Mark the head.

2. Store the addresses of the nodes in a hash table (any data structure with fast lookups) as you traverse the linked list.

3. For every node, keep checking if you've visited it before. If you have, and it's the the head, then the linked list is circular. If it's a different node, then the linked list has a loop, but is not circular. Stop in either case.

4. If you reach the tail of the linked list, also not circular.

Answer 2

maybe check this
https://code.sololearn.com/cCqNp7EcxQPU

Answer 3

ok here is my code.
I traverse linked list simultaneously with two pointers. One pointer traverse by twice the speed by first by skipping one node.
Hence if it is circular at some point they will point to same node because of different speed.
if it's not circular, pointer will become null at some point

https://code.sololearn.com/crwg6pI65GyX/?ref=app

Answer 4

but why for every node need to check.
instead we can just check that at last if our ptr points to START or starting node.

Answer 5

code learner genius!! i haven't even think of this kind of method to check circular😆

Answer 6

code learner very nice! Though having a loop need not be the same as being circular. Slight modification would do it ;)

Flandre Scarlet It's Floyd's tortoise and the hare algorithm https://en.m.wikipedia.org/wiki/Cycle_detection

Answer 7

How then, do we know that we've reached the last node? What if the linked list looks like

a -> b -> c -> b

It'd be an endless loop of b and c, right?

Answer 8

hello anybody up, so i have a flow chart representation assignment, can I get someone to help me out im a beginner on here