import java.util.
*;
class Node {
int num;
Node next;
Node(int val) {
num = val;
next = null;
}
}
class Main {
// Insert a node into the linked list
static Node insertNode(Node head, int val) {
Node newNode = new Node(val);
if (head == null) {
head = newNode;
return head;
}
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
return head;
}
// Display the linked list
static void display(Node head) {
Node temp = head;
while (temp.next != null) {
System.out.print(temp.num + " -> ");
temp = temp.next;
}
System.out.println(temp.num + " -> NULL");
}
// Create a cycle in the linked list
static void createCycle(Node head, int a, int b) {
int cnta = 0, cntb = 0;
Node p1 = head;
Node p2 = head;
while (cnta != a || cntb != b) {
if (cnta != a) {
p1 = p1.next;
cnta++;
}
if (cntb != b) {
p2 = p2.next;
cntb++;
}
}
p2.next = p1; // Create the cycle
}
// Detect if a cycle exists in the linked list
static boolean cycleDetect(Node head) {
if (head == null) return false;
Node fast = head;
Node slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// If slow and fast meet, a cycle exists
if (fast == slow) return true;
}
return false;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
// Input the size of the linked list
System.out.print("Enter the number of nodes in the linked list: ");
int n = sc.nextInt();
Node head = null;
// Input the elements of the linked list
System.out.println("Enter the elements of the linked list:");
for (int i = 0; i < n; i++) {
int m = sc.nextInt();
head = insertNode(head, m);
}
// Display the original linked list
System.out.println("Original Linked List:");
display(head);
// Input the position to create a cycle
System.out.print("Enter the position to create a cycle: ");
int a = sc.nextInt();
createCycle(head, 1, a); // Create a cycle in the list
// Detect if a cycle exists
if (cycleDetect(head)) {
System.out.println("Cycle detected");
} else {
System.out.println("Cycle not detected");
}
sc.close();
}
}
input :
import java.util.*;
class Node {
int num;
Node next;
Node(int val) {
num = val;
next = null;
}
}
class Main {
// Insert a node into the linked list
static Node insertNode(Node head, int val) {
Node newNode = new Node(val);
if (head == null) {
head = newNode;
return head;
}
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = newNode;
return head;
}
// Display the linked list
static void display(Node head) {
Node temp = head;
while (temp.next != null) {
System.out.print(temp.num + " -> ");
temp = temp.next;
}
System.out.println(temp.num + " -> NULL");
}
// Create a cycle in the linked list
static void createCycle(Node head, int a, int b) {
int cnta = 0, cntb = 0;
Node p1 = head;
Node p2 = head;
while (cnta != a || cntb != b) {
if (cnta != a) {
p1 = p1.next;
cnta++;
}
if (cntb != b) {
p2 = p2.next;
cntb++;
}
}
p2.next = p1; // Create the cycle
}
// Detect if a cycle exists in the linked list
static boolean cycleDetect(Node head) {
if (head == null) return false;
Node fast = head;
Node slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
// If slow and fast meet, a cycle exists
if (fast == slow) return true;
}
return false;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
// Input the size of the linked list
System.out.print("Enter the number of nodes in the linked list: ");
int n = sc.nextInt();
Node head = null;
// Input the elements of the linked list
System.out.println("Enter the elements of the linked list:");
for (int i = 0; i < n; i++) {
int m = sc.nextInt();
head = insertNode(head, m);
}
// Display the original linked list
System.out.println("Original Linked List:");
display(head);
// Input the position to create a cycle
System.out.print("Enter the position to create a cycle: ");
int a = sc.nextInt();
createCycle(head, 1, a); // Create a cycle in the list
// Detect if a cycle exists
if (cycleDetect(head)) {
System.out.println("Cycle detected");
} else {
System.out.println("Cycle not detected");
}
sc.close();
}
}
Sample Test case:
Enter the number of nodes in the linked list: 5
Enter the elements of the linked list:
1 2 3 4 5
Original Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> NULL
Enter the position to create a cycle: 4
Cycle detected
Time Complexity:O(n)
Space:O(1)
