Check Linked List Has Cycle - Coding in A Smart Way

Check Linked List Has Cycle - Coding in A Smart Way

Written by truongkhanh on Problem: Check Linked List Has Cycle Given a linked list, check if it has cycle. For example, in the below figure, the first linked list does not have cycle while the second linked list has. Discussion Linked list with cycle may cause the program having infinite iteration. Therefore, checking linked list with cycle is required. The most straightforward approach is during iterating the list, given a node, we check whether that node exists before. If we use a Set data structure to store the visited nodes, the program runs in O(N) and uses O(N) memory. If we do not use Set, we can make a second iteration from the beginning of the list to check whether that node is visited before. Thus, the program runs in O(N2) and use O(1) memory. In this post, I will introduce you a new technique which is often used to solve many problems in linked list. We will use 2 running pointers during the iteration to check if linked list has cycle. As discussed,

Read full article from Check Linked List Has Cycle - Coding in A Smart Way