713150. Find the first node of loop in linked list
Find the First Node of Loop in Linked List
Summary
Given a linked list with a loop, find the first node of the loop. This problem involves understanding the concept of loops in linked lists and implementing an efficient algorithm to detect the start of the loop.
Detailed Explanation
The given linked list has a cycle or a loop. A loop occurs when there is a reference from some node back to previous nodes, thus forming a cycle. We can solve this problem using Floyd's Cycle-Finding Algorithm (also known as the "tortoise and the hare" algorithm). This algorithm works by having two pointers, one that increments one step at a time and another that increments two steps at a time. If there is no loop, these two pointers will never meet. But if there is a loop, they will eventually meet.
Here's how we can implement this:
- Initialize the two pointers,
slowandfast, to the head of the linked list. - Move the
slowpointer one step at a time and thefastpointer two steps at a time. - If there is no loop, these two pointers will never meet. But if there is a loop, they will eventually meet at some node inside the loop.
- Once we detect the meeting point, reset the
slowpointer to the head of the linked list and move both pointers one step at a time. They will meet again at the start of the loop.
The steps are visualized below:
A -> B -> C -> D -> E -> F
| |
V V
S (slow) -> A -> B -> C -> D -> ... T (fast)
Time Complexity: O(n) Space Complexity: O(1)
Optimized Solutions
Java
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) return null;
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) break;
}
if (fast == null || fast.next == null) return null;
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}