Detect Loop in Linked List

Slug: detect-loop-in-linked-list

Difficulty: Medium

Id: 700099

Topic Tags: Linked List, two-pointer-algorithm, Data Structures, Algorithms

Company Tags: Paytm, VMWare, Accolite, Amazon, OYO Rooms, Samsung, Snapdeal, D-E-Shaw, Hike, MakeMyTrip, Walmart, MAQ Software, Adobe, SAP Labs, Qualcomm, Veritas, Mahindra Comviva, Lybrate

Summary

Detecting a loop in a linked list is a fundamental problem in computer science. Given the head of a singly linked list, determine if there's a cycle (loop) present in the linked list. A cycle is when a node points back to a previous node rather than NULL.

Detailed Explanation

To detect a loop in a linked list, we can use Floyd's Cycle Detection Algorithm, also known as the "tortoise and the hare" algorithm. This algorithm takes advantage of the fact that if there is a cycle, then eventually the two pointers will meet at some node within the cycle.

Here are the steps to solve this problem:

1. Initialize two pointers, slow and fast, both starting from the head of the linked list.
2. Move slow one step at a time and move fast two steps at a time.
3. If there is no loop in the linked list, then fast will reach the end of the linked list before meeting slow.
4. If there is a cycle, then fast and slow will meet at some node within the cycle.
5. Once we've found the meeting point, we can move both pointers back to the head of the linked list and move them one step at a time until they meet again. This will be the start of the cycle.

Time Complexity:

The time complexity is O(n) where n is the number of nodes in the linked list.

Space Complexity:

The space complexity is O(1) as we only use a constant amount of space to store our pointers and variables.

Optimized Solutions

Java