Home Linked List Find cycle in a linked list. (Method 1)

Find cycle in a linked list. (Method 1)

by nikoo28
1 comment

Question: Given a linked list, return the node where the cycle begins. If there is no cycle, return null.


Output: 0

We are given a linked list which may or may not have a loop. A loop in a linked list means that if we keep doing a next, we will never reach null. Thus, we can be clear of a fact that if we reach null, then the list does not have a loop.

So how do we detect if there is a loop in the linked list. One method that immediately comes to our mind is that if a value is encountered twice, there may be a chance that the linked list has a loop. Thus, we can use Sets to keep track of all the values traversed.

Algorithm

  • Allocate a Set to store ListNode references.
  • Traverse the list, checking visited for containment of the current node.
  • If the node has already been seen, then it is necessarily the entrance to the cycle.
  • If any other node were the entrance to the cycle, then we would have already returned that node instead.
  • Otherwise, the if condition will never be satisfied, and our function will return null.

The algorithm necessarily terminates for any list with a finite number of nodes, as the domain of input lists can be divided into two categories: cyclic and acyclic lists. An acyclic list resembles a null-terminated chain of nodes, while a cyclic list can be thought of as an acyclic list with the final null replaced by a reference to some previous node. If the while loop terminates, we return null, as we have traversed the entire list without encountering a duplicate reference. In this case, the list is acyclic. For a cyclic list, the while loop will never terminate, but at some point the if condition will be satisfied and cause the function to return.

// Template for a linked list node class ListNode { int value; ListNode next; } public class Solution { public ListNode detectCycle(ListNode head) { Set<ListNode> visited = new HashSet<ListNode>(); ListNode node = head; // Traverse the list while (node != null) { // If the node is already present in the Set // this is a loop and we need to return it. if (visited.contains(node)) { return node; } visited.add(node); node = node.next; } // No loop found return null; } }

Time Complexity: O(n)
Space Complexity: O(n)

A sample problem can be found here.

A method with constant space can be found here.

Find cycle in a Linked List (Method 2)

1 comment

You may also like

1 comment

Find cycle in a linked list. (Method 2) - Study Algorithms June 5, 2020 - 03:39

[…] Length of longest palindrome that can be built… Find cycle in a linked list. (Method 2) Find cycle in a linked list. (Method 1) Next Greater Element in an array. [NGE] Prime factors of a number. [Prime Factorization] […]

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More