+ 5

How do you check if a given linked list contains a cycle? How do you find the starting node of the cycle?

19th Aug 2019, 12:48 PM
Perez
Perez - avatar
3 Answers
+ 4
Use two pointers. Advance one pointer by one increment/node and the other by two. Repeat the process, checking at each iteration if the value of the two pointers are equal or if one has reached the end of the list. If the pointers are equal, then the linked list has a cycle and both pointers would point to the starting node of the cycle. If the end of the list/null node is reached, there is no cycle.
19th Aug 2019, 2:26 PM
Sonic
Sonic - avatar
+ 2
Is that even allowed, such a cycle? Can't you prevent that by testing if the same pointer already exists in that list, before you store one? (I don't know about this well enough; I'll follow this and see what we will learn. 😉)
19th Aug 2019, 12:57 PM
HonFu
HonFu - avatar
+ 2
Myself am looking into that. ..I saw the question elsewhere
19th Aug 2019, 1:06 PM
Perez
Perez - avatar