Circular Linked List (can't figure out the solution)

#1

if i generated a LL for a input 1 2 3 4 5 2 3 -1
then at the run time my LL will be generated like
1 -> 2 -> 3 -> 4->5->2->3…
then how can i apply floyd Cycle Detection Algorithm to it…i am getting confused

#2

Just create a function that accepts a LL and applies FW to it and returns the loop start point. As for the input, you just keep appending the incoming elements till you encounter a 1. The moment you encounter a -1 send this LL to that function for processing and print out the answer.

#3

import java.util.*;
public class Main {
static Scanner sc = new Scanner(System.in);

private class Node {
	int data;
	Node next;
}

private Node head;
private Node tail;
private int size;

public Main() {
	this.head = null;
	this.tail = null;
	this.size = 0;
}

public int size() {
	return this.size;
}

public void add(int item) {
	Node nn = new Node();
	nn.data = item;
	nn.next = null;

	if (this.size > 0) {
		this.tail.next = nn;
	}

	if (this.size == 0) {
		this.head = nn;
		this.tail = nn;
		this.size++;
	} else {
		this.tail = nn;
		this.size++;
	}
}

public void display() {
	Node temp = this.head;
	while (temp != null) {
		System.out.print(temp.data + " ");
		temp = temp.next;
	}
	System.out.println("");
}

public void Cycle() {
	Node slow = this.head;
	Node fast = this.head.next.next;
	Node prv = null;
	
	while (fast != slow) {
		prv = slow;
		if (fast.next == null) {
			fast = this.head.next;
			slow = slow.next;
		} else {

			fast = fast.next.next;
			slow = slow.next;
		}
	}
	prv.next = null;
	this.tail = prv;
}

public static void main(String[] args) {

	Main l1 = new Main();
	int val = sc.nextInt();
	while (val != -1) {
		l1.add(val);
		val = sc.nextInt();
	}
	l1.Cycle();
	l1.display();
}

}

#4

its running for 1 2 3 4 5 2 3 -1 but for rest test case it’s showing run error…can you pls help me with this

#5

that’s because you have accessed node.next.next many times without actually checking if node.next != null

#6

for input 1 2 3 4 5 2 3 -1
my LL will be LL will be 1 -> 2 -> 3 -> 4->5->2->3->end
so there just duplicate element 2,3 there is no linking between first coming 2->3 and last coming 2->3 hence it is forming a straight path, not a cycle
so how will FW algo work…i mean how can i make a cycle out of the input for the Algo to work

#7

No, I think you need to read the question again. All the nodes have distinct values, i.e. once you encounter some value in the input that has already occured make the link to that Node which you have used for this value before. This can be done quite easily using HashMap.