Question

In: Computer Science

You are given a singly linked list. Write a function to find if the linked list...

You are given a singly linked list. Write a function to find if the linked list contains a cycle or not. A linked list may contain a cycle anywhere. A cycle means that some nodes are connected in the linked list. It doesn't necessarily mean that all nodes in the linked list have to be connected in a cycle starting and ending at the head. You may want to examine Floyd's Cycle Detection algorithm.

/*This function returns true if given linked 
list has a cycle, else returns false. */
static boolean hasCycle( Node head) 

Solutions

Expert Solution

The java code to find the loop or cycle in the linked list which may be present at any place in the linked list.

For the function to find the cycle is present or not we use Floyd's Cycle Detection algorithm.

static boolean hasCycle(Node head){

Node slow_node=head;

Node fast_node=head;

while(slow_node != null && fast_node !=null && fast_node.next !=null){

slow_node = slow_node.next;

fast_node = fast_node.next.next;

if(slow_node==fast_node){

System.out.println("Cycle is present");

return true;

}  

}

return flase;

}

In this code, we first take two nodes slow and fast. Assign the linked list head value to them and start the algorithm condition. By checking the conditions of null we run the while loop which increases the value of slow node by next and fast node by next, next. If there is loop then definitely this fast and slow values will be equal and we can find the loop is present.

I have not written code about Node or main function as it is not required according to the question given.

I hope you got the answer and understand it. Any doubts ask in comments I will help with it.

Thank you:):)


Related Solutions

Evaluate and write an algorithm to find the largest item in an unsorted singly linked list...
Evaluate and write an algorithm to find the largest item in an unsorted singly linked list with cells containing integers
Given a singly linked list that contains a sequence of integers, write a method that loop...
Given a singly linked list that contains a sequence of integers, write a method that loop through each elements in this singly linked list with O(n) time complexity, and let each elements multiply 6, return the result. code needed in java! thanks in advance!
C++ Question Write a code for :- public List Palindrome(); //Check whether a given singly linked...
C++ Question Write a code for :- public List Palindrome(); //Check whether a given singly linked list is palindrome or not. Input: a -> b-> NULL a -> b -> a-> NULL s -> a -> g -> a -> r-> NULL r -> a -> d -> a -> r-> NULL Output: not palindrome palindrome not palindrome palindrome Note:- Code should work on MS-Visual Studio 2017 and provide outputs with code
Exercise 1: Write a program in Java to manipulate a Singly Linked List: 1. Create Singly...
Exercise 1: Write a program in Java to manipulate a Singly Linked List: 1. Create Singly Linked List 2. Display the list 3. Count the number of nodes 4. Insert a new node at the beginning of a Singly Linked List. 5. Insert a new node at the end of a Singly Linked List 6. Insert a new node after the value 5 of Singly Linked List 7. Delete the node with value 6. 8. Search an existing element in...
c. You are given the following Java files: SLL.java that implements generic Singly Linked List, with...
c. You are given the following Java files: SLL.java that implements generic Singly Linked List, with class SLLNode listed as inner class. TestIntegerSLL.java that tests the SLL class by using a linked list of Integer. In SLL class add the following method:                                                                    public void moveToEnd (int i) It will move the element at the i -th position to the end of the list. You can assume i to be within the list, and that the first element has the...
I was supposed to conver a singly linked list to a doubly linked list and everytime...
I was supposed to conver a singly linked list to a doubly linked list and everytime I run my program the output prints a bunch of random numbers constantly until I close the console. Here is the code. #include <stdio.h> #include <stdlib.h> #include <string.h> #include <stdbool.h> struct node { int data; struct node *next; struct node *prev; }; //this always points to first link struct node *head = NULL; //this always points to last link struct node *tail = NULL;...
Write a java method to swap between two values in a singly linked list
Write a java method to swap between two values in a singly linked list
What will be the final linked-list after executing the following method on the given input singly...
What will be the final linked-list after executing the following method on the given input singly linked-list? Consider that the singly linked-list does not have a tail reference. Input: 1->2->3->4->5->6->7->8->null                                                    void method(list){ if(list.head == null) return; Node slow_ref = list.head; Node fast_ref = list.head; Node prevS = null; Node prevF = null; while(fast_ref != null && fast_ref.next != null){ prevS = slow_ref; slow_ref = slow_ref.next; prevF = fast_ref; fast_ref = fast_ref.next.next; } prevS.next = slow_ref.next; prevF.next.next = slow_ref; slow_ref.next...
In C++, Implement the queue ADT with a singly linked list
In C++, Implement the queue ADT with a singly linked list
HI i will write user's manual for a doubly/singly linked list , How can i write...
HI i will write user's manual for a doubly/singly linked list , How can i write User's manual ?
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT