Can you suggest me the better solution.
i know about floyds Cycle detection but it does not work here.
import java.util.*;
public class Main {
public static void main(String args[]) throws Exception {
Scanner scan = new Scanner(System.in);
LinkedList l = new LinkedList();
while(true){
int n = scan.nextInt();
if(n!=-1){
l.addLast(n);
}else{
break;
}
}
l.loopFreeDisplay();
}
}
class LinkedList{
private class Node{
int data;
Node next;
}
private Node head; // To hold the address of the first node
private Node tail; // To hold the address of the Last Node
private int size; // no. of nodes
// functions
public void addFirst(int item) // to add the node at First Position
{
Node nn = new Node(); // creating new Node [item | address of next Node]
nn.data = item;
nn.next = null;
if(size ==0) // this is my first node so my head is the address of this node as well as the tail
{
this.head = nn; //nn hold the address of my node
this.tail = nn;
this.size++;
}else // i already have first node [] head->[]-[]-[]-[]-[]
{ nn.next = this.head; // so my new node will hold the address of my first node
this.head = nn; // my head will shift to the new added node
this.size++;
}
}
public void addLast(int item){
// creating the node
Node nn = new Node();
nn.data = item;
nn.next= null;
//Attaching node
if(size==0){
this.head = nn;
this.tail = nn;
this.size++;
}else{
// Now my last node will become 2nd LASt so my tail.next will hold the address of my newly added node
this.tail.next = nn;
this.tail = nn;
this.size++;
}
}
public int getFirst() throws Exception{
//return the data of the first node of the linked list
if(this.size ==0){
throw new Exception("LL is Empty");
}
return this.head.data;
}
public int getLast()throws Exception{
//return the data of the Last node of the linked list
if(this.size ==0){
throw new Exception("LL is Empty");
}
return this.tail.data;
}
public int getAt(int index) throws Exception // return the data at the particular index
{
if(size==0){
throw new Exception("LL is Empty");
}
if(index<0|| index>=size){
throw new Exception("Invalid Index");
}
Node temp = this.head;
for(int i=1;i<=index;i++){
temp = temp.next;
}
return temp.data;
}
public Node getNodeAt(int index) throws Exception{
// to get the node adderess at particular index
if(size==0){
throw new Exception("LL is Empty");
}
if(index<0|| index>=size){
throw new Exception("Invalid Index");
}
Node temp = this.head;
for(int i =1;i<=index;i++){ // see if index is 0 then it will return head.data the first node
temp = temp.next;
}
return temp;
}
public void addAt(int item, int index) throws Exception{
if(size==0){
throw new Exception("LL is Empty");
}
if(index<0|| index>size) // yaha pe = nhi ayega kyuki ham last me add kar sakte hai
{
throw new Exception("Invalid Index");
}
if(index == 0){
addFirst(item);
}
else if(index == this.size){
addLast(item);
}
else{
Node nn = new Node();
nn.data = item;
nn.next = null;
//attach
Node nm1 = getNodeAt(index-1);
Node np1 = nm1.next; // address of the node which will succed the added node
nm1.next = nn;
nn.next = np1;
this.size++;
}
}
//Removing
public int removeLast()throws Exception{
// tail hold the last node
if(size==0){
throw new Exception("LL is Empty");
}
int rv = tail.data;
if(size == 1){ // that means there exist one node which is last and first
this.tail = null;
this.head = null;
this.size=0;
}else{
// now we have to shift tail to the previous node which can not be done directly so we need to access the node behind tail size-1
Node sizem2 = getNodeAt(this.size-2);
this.tail = sizem2; //shifting tail
sizem2.next = null; //by this we removed the link between last and 2nd last node
this.size--;
}
return rv;
}
public int removeFirst() throws Exception{
if(size==0){
throw new Exception("LL is Empty");
}
int rv = this.head.data;
if(size ==1){
this.head =null;
this.tail = null;
this.size=0;
}else{
this.head = this.head.next;
this.size--;
}
return rv;
}
public int removeNodeAt(int index)throws Exception{
if(size==0){
throw new Exception("LL is Empty");
}
if(index<0|| index>=size) // yaha pe = nhi ayega kyuki ham last me add kar sakte hai
{
throw new Exception("Invalid Index");
}
if(index==0){
return removeFirst();
}
else if(index == this.size-1){
return removeLast();
}else{
Node nm1 = getNodeAt(index-1); //[nm1] -- [n] -- [np1] we have to remove middle node
Node n = nm1.next;
Node np1 = n.next;
nm1.next = np1;
this.size--;
return n.data;
}
}
public void display() throws Exception{
if(this.size ==0){
throw new Exception("LL is Empty");
}
Node temp = head;
while(temp!=null){
System.out.print(temp.data+" ");
temp = temp.next;
}
}
public void reverseData() throws Exception{
int left =0;
int right = this.size-1;
//System.out.println(right);
while(left<right){
Node l = getNodeAt(left);
Node r = getNodeAt(right);
int temp = l.data;
l.data = r.data;
r.data = temp;
left++;
right--;
}
}
// kth element from last without size Ram and sita start from 0 to 10. first ram runs k steps them sita starts so when ram finish sita will ne at 10-k :Logics
public int nodeAtKLast(int k){
Node temp = this.head;
Node temp2 = this.head;
while(k>0){
temp = temp.next;
}
while(temp.next!=null){
temp2 = temp2.next;
temp.next = temp.next;
}
return temp2.data;
}
public void reversePointers() throws Exception{
Node prev = this.head;
Node curr = prev.next;
while(curr!=null){
Node ahead = curr.next;
curr.next = prev;
prev = curr;
curr = ahead;
}
//swap head and tail
Node t = this.tail;
this.tail = this.head;
this.head = t;
//tail.next should be null
this.tail.next = null;
}
public Node loopOver() throws Exception{
for(int i =0;i<this.size-1;i++){
for(int j = i+1; j<this.size-1;j++){
Node ptr1 = getNodeAt(i);
Node ptr2 = getNodeAt(j);
if(ptr1.data==ptr2.data){
return ptr2;
}
}
}
return this.tail;
}
public void loopFreeDisplay() throws Exception{
Node temp = this.head;
Node capture = loopOver();
while(temp.next!= capture.next){
System.out.print(temp.data+ " ");
temp = temp.next;
}
}
public int mid(){
Node slow = this.head;
Node fast = this.head;
// finding mid of the linked list without size and in one traversal : logic used Speed of one pinter is twice of other if one completes its journey then other will be in mid
//fast.next.next is fast = fast.next and then fast =fast.next again
while(fast.next!=null && fast.next.next!=null){
fast = fast.next.next; // double jump
slow = slow.next;
}
return slow.data;
}
public boolean isEmpty(){
return this.size==0;
}
public int size(){
return this.size;
}
}