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; } }
Code language: Java (java)

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)

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] […]

Comments are closed.

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