Method 2 Linked List (make visited nodes)

Lesson 4 of 10 • 0 upvotes • 5:47mins

Rakesh Naga Chinta

Method 2 linked list How to detect loop using Floyd's cycle detection algorithm This solution requires modifications to basic linked list data structure. Have a visited flag with each node. Traverse the first linked list and keep marking visited nodes. Now traverse second linked list, If you see a visited node again then there is an intersection point, return the intersecting node. This solution works in O(m+n) but requires additional information with each node. A variation of this solution that doesn’t require modification to basic data structure can be implemented using hash. Traverse the first linked list and store the addresses of visited nodes in a hash. Now traverse the second linked list and if you see an address that already exists in hash then return the intersecting node.