Problem Statement:- Given a circular linked list, implement an algorithm which returns node at the beginning of the loop.
DEFINITION:-
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C
here is the code ...
DEFINITION:-
Circular linked list: A (corrupt) linked list in which a node’s next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
input: A -> B -> C -> D -> E -> C [the same C as earlier]
output: C
here is the code ...
public class Q5 {
public static void main(String[] args) {
Node head = new Node(1); // head node of the linked list
Node node1 = new Node(2);
head.next = node1;
Node node2 = new Node(3);
node1.next = node2;
Node node3 = new Node(4);
node2.next = node3;
Node node4 = new Node(5);
node3.next = node4;
Node node5 = new Node(6);
node4.next = node5;
Node node6 = new Node(7);
node5.next = node6;
node6.next = node3; // here loop appears
findNodeAtbeg(head);
}
public static void findNodeAtbeg(Node head) {
Node slow = head; //slow pointer
Node fast = head; //fast pointer
while (fast != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null) {
System.out.print("There is no loop exit");
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
System.out.println("Node where loop begins contains data item as - "
+ fast.data);
}
}
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}