700332. Remove loop in Linked List
Remove Loop in Linked List
Summary
Given a linked list, remove the loop if it exists. The linked list can contain multiple nodes with duplicate values and the loop can start from any node.
This problem is about manipulating a linked list to detect and remove a loop that might be present in the list. The key concepts involved are traversing the linked list and using two pointers technique to detect the loop.
Detailed Explanation
The approach to solve this problem involves two-pointer technique, where we move one pointer faster than the other. If there is no loop, these two pointers will eventually meet at some node. However, if there is a loop, they will meet at some node within the loop. Once we detect the meeting point, we reset one of the pointers to the starting point and then move both pointers at the same speed. The meeting point of these two pointers would be the start of the loop.
Here's the step-by-step breakdown:
- Initialize two pointers
slowandfastto the head of the linked list. - Move the
fastpointer one step at a time, while moving theslowpointer one step at a time. - If there is no loop,
fastwill eventually meetslow. - If there is a loop,
fastandslowwill meet within the loop. - Reset
slowto the starting point and move bothslowandfastone step at a time. - The meeting point of these two pointers would be the start of the loop.
Time complexity: O(n), where n is the number of nodes in the linked list. Space complexity: O(1).
Optimized Solutions
Java
public ListNode detectAndRemoveLoop(ListNode head) {
if (head == null || head.next == null) {
return head;
}
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 head;
}
slow = head;
while (slow.next != fast) {
slow = slow.next;
fast = fast.next;
}
slow.next = null;
return head;
}