Length of Loop in Linked List
Medium Problems of Singly Linked List DSA practice problem on Onlearn.
Difficulty: easy.
Topics: Determine the length of a loop in a linked list; return 0 if there is no loop., Linked List, Node, Pointer, Time Complexity, Space Complexity, Big O Notation, Hashing, Map, Two Pointers, Algorithm, space complexity, linked list, hash map, cycle detection, time complexity analysis, two pointer technique, Cycle Detection (Floyd's Algorithm).
Problem Statement Given the head of a singly linked list, determine the length of a loop present in the linked list. If no loop is present, return 0. A loop (or cycle) in a linked list exists if a node in the list can be reached again by continuously following the next pointers. The length of the loop is the number of nodes within the cycle. Input Specification The first line contains an integer N (1 <= N <= 10^5), the number of nodes in the linked list. The second line contains N integers, representing the data values of the nodes from head to tail. The third line contains an integer pos (0 indexed). If pos is 1, there is no loop. If pos is a non negative integer, it indicates that the next pointer of the last node points to the node at index pos (0 indexed). Output Specification Return an integer representing the length of the loop. If no loop exists, return 0. Sample Test Cases Example 1: Input: 5 1 2 3 4 5 2 Output: 3 Explanation: A cycle exists in the linked list starting at node with value 3 (0 indexed position 2) 4 5 and then back to 3. There are 3 nodes (3, 4, 5) present in this cycle. Example 2: Input: 6 1 2 3 4 9 9 1 Output: 0 Explanation: In this example, the linked list is linear and does not have a loop.