Task Description
Detect if a given linked list has a loop. If it has a loop, find the starting node of the loop.Solution 1 : Simple Solution
When I first came across this problem, the solution that I thought of was to traverse through all the nodes and for every node, check if we have already encountered this node. If we ecnounter a node which has already been visited before, then the linked list has a loop. We can efficiently check if the node has already been visited by maitaining a HashSet of already visited nodes. The starting node of the loop will the first repeated node encountered.If the linked list does not have a loop, then the traversal of the list will terminate without encountering any repeated node.
Implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//-----------------------------------------------------------------------------------
/**
* Detects a loop in a given LinkedList
* Based upon keeping track of already visited Nodes
* @param head head of the LinkedList
* @return start of loop if it exists, otherwise null
*/
public Node detectLoop(Node head) {
Set<Node> visitedNodes = new HashSet<Node>();
Node node = head;
while (node != null) {
if (visitedNodes.contains(node)) { // loop detected. node is the start of the loop
return node;
} else {
visitedNodes.add(node);
node = node.next;
}
}
return null; // no loop
} // detectLoop
//------------------------------------------------------------------------------------
Complexity
In this method, we traverse through all the nodes only once except the first repeated node if it exists. The repeated node will be traversed twice. Checking for a repeated node using HashSet is a constant time operation. ∴ The Time Complexity of this method is O(n) time.But we are saving each traversed node into a HashSet. ∴ The Space Complexity of this method is also O(n) time.
Solution 2: Efficient Solution (Floyd's Method)
Floyd gave a more efficient method than discussed above. This method is efficient in terms of the space used. Time Complexity remains O(n) while the Space Complexity is constant time O(1).Principle
Floyd's method is based upon a principle that if two pointers - one moving at the speed of one node at a time and another at twice the speed of the first, are circulating in a loop, then they will always meet at a node.
At any time, if Faster Pointer is just behind the Slower Pointer, then in the next step, they will meet.
At any time, if the Faster Pointer is just aheadd of the Slower Pointer, this position is possible only if they have met in the previous step.
Detecting the Loop
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Node faster = head;
Node slower = head;
// detect loop
while (faster != null && faster.next != null) {
faster = faster.next.next;
slower = slower.next;
if (faster == slower) { // loop detected
break;
}
}
if (faster != slower) return null; // loop not detected
Mathematics - Identify the Start of Loop
Let, when the two pointers intersect,
m=length of the non−loop branch
n=length of the loop
k=length from starting point of the loop to the point of intersection
x=number of complete loops made by the slower pointer
y=number of complete loops made by the faster pointer
Now,
distance traveled by faster pointer (F)=m+k+yn
distance traveled by slower pointer (S)=m+k+xn
Since, faster pointer has moving at double the speed of slower pointer,
F=2S
=>m+k+yn=2(m+k+xn)
=>m+k+yn=2(m+k)+2xn
=>m+k=yn−2xn
=>m+k=n(y−2x)
=>∵faster pointer is moving at double speed, (y−2x)>=1 and is ALWAYS an Integer.
=>m+k=certain number of COMPLETE loop cycles
So, we can conclude that,
- If Two Pointers (move at the same speed) start moving at the same time, one start from beginning of the linked list and another start from beginning of the loop, by the time the first Pointer travels m+k nodes, the second Pointer will make certain number of complete loop and reach the beginning the loop again.
- If the first pointer moves only m nodes, then the second pointer will complete some loop and travel n−k nodes.
- If the second pointer starts from the point of intersection instead of beginning of the loop, both of the pointer will meet at the beginning of the loop. This is our REQUIRED start of the loop.
Compute Start of the Loop
So based upon the theory above, we can find the start of the loop by following way:- When the two pointers meet (the loop is detected), keep one pointer at the same location and move the other to the beginning of the linked list.
- Now move the two pointers at the same speed - one node at a time.
- When the two pointers meet, the meeting point will be the beginning of the loop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// detect start of loop
faster = head;
while (faster != slower) {
faster = faster.next;
slower = slower.next;
}
return faster;
Complete Implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* File: DetectLoopInLinkedList.java
* Created: 2018-05-09
* Author: Sabbir Manandhar
*
* Copyright (c) 2018 Hogwart
*/
import java.util.HashSet;
import java.util.Set;
/**
* Detect Loop in a Linked List
*
* @author Sabbir Manandhar
* @version 1.0
*/
public class DetectLoopInLinkedList {
public static void main(String[] args) {
DetectLoopInLinkedList detectLoopInLinkedList = new DetectLoopInLinkedList();
int i = 1;
Node head = detectLoopInLinkedList.new Node(i++);
Node tail = head;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++); // 11
tail = tail.next;
Node loopBegin = tail;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
tail = tail.next;
tail.next = detectLoopInLinkedList.new Node(i++);
// No Loop
Node loopStart1 = detectLoopInLinkedList.detectLoop(head);
Node loopStart2 = detectLoopInLinkedList.detectLoopFloydMethod(head);
System.out.println(loopStart1 == null && loopStart2 == null ? "SUCCESS: Loop Not Found" : "Failure");
// Crate Loop at 11
tail = tail.next;
tail.next = loopBegin;
loopStart1 = detectLoopInLinkedList.detectLoop(head);
loopStart2 = detectLoopInLinkedList.detectLoopFloydMethod(head);
System.out.println(loopStart1 == loopStart2 ? "SUCCESS: Loop Start Found: " + loopStart1.value : "Failure");
} // main
//-----------------------------------------------------------------------------------
/**
* Detects a loop in a given LinkedList
* Based upon keeping track of already visited Nodes
* @param head head of the LinkedList
* @return start of loop if it exists, otherwise null
*/
public Node detectLoop(Node head) {
Set<Node> visitedNodes = new HashSet<Node>();
Node node = head;
while (node != null) {
if (visitedNodes.contains(node)) { // loop detected. node is the start of the loop
return node;
} else {
visitedNodes.add(node);
node = node.next;
}
}
return null; // no loop
} // detectLoop
//------------------------------------------------------------------------------------
/**
* Detect Loop in a LinkedList using Floyd's Method
* @param head Head of the LinkedList
* @return start of loop if it exists, otherwise null
*/
public Node detectLoopFloydMethod(Node head) {
Node faster = head;
Node slower = head;
// detect loop
while (faster != null && faster.next != null) {
faster = faster.next.next;
slower = slower.next;
if (faster == slower) { // loop detected
break;
}
}
if (faster != slower) return null; // loop not detected
// detect start of loop
faster = head;
while (faster != slower) {
faster = faster.next;
slower = slower.next;
}
return faster;
} // detectLoopFloydMethod
//------------------------------------------------------------------------------------
/**
* Class to represent Linked List Node
*/
public class Node {
Node next;
int value;
public Node(int value) {
this.value = value;
} // Node
} // Node
} // DetectLoopInLinkedList
No comments:
Post a Comment