Amazon Interview Question
Quality Assurance EngineersCountry: United States
Interview Type: In-Person
{ //Returns true if list is circular, else false
class Node{
int data;
Node next;
public boolean checkCircular(Node head){
if(head == NULL || head.next == NULL)
return false;
Node temp = head.next;
while(temp != NULL){
if(temp==head) return true;
temp = temp.next;
}
return false;
}
}
}
class Node{
public int data;
public Node next;
Node(int data){
this.data = data;
}
}
public class ListOperations{
public Node checkCircular(Node head){
if(head == null){
return null;
}
Node slow, fast;
slow = head;
fast = head;
do{
slow = slow.next;
if(fast.next != null)
fast = fast.next.next;
else
fast = null;
}while(fast != slow && fast != null);
if(fast == slow){
return fast;
}
else
return null;
}
public static void main(String [] args){
Node a1 = new Node(1);
Node a2 = new Node(2);
Node a3 = new Node(3);
Node a4 = new Node(4);
Node a5 = new Node(5);
Node a6 = new Node(6);
Node a7 = new Node(7);
Node a8 = new Node(8);
Node a9 = new Node(9);
Node a10 = new Node(10);
a9.next = a10;
a8.next = a9;
a7.next = a8;
a6.next = a7;
a5.next = a6;
a10.next = a5;
a4.next = a5;
a3.next = a4;
a2.next = a3;
a1.next = a2;
ListOperations listOps = new ListOperations();
System.out.println(listOps.checkCircular(a1)==null?false:true);
}
}
As it is not clearly mentioned that either we have to check complete circular or inner circular list. so have to detect any circular relation exist in linkedlist.
We can use HashMap to store each node using this logic.
Object obj = new Object;
if(!map.contains(node))
map.put(node,obj);
else
return true;
class Node
{
Node next;
int info;
Node(int data)
{
info = data;
next = null;
}
Node createList()
{
Node start = new Node(1);
Node mid1 = new Node(2);
Node mid2 = new Node(3);
Node mid3 = new Node(4);
Node end = new Node(5);
start.next=mid1;
mid1.next=mid2;
mid2.next=mid3;
mid3.next=end;
end.next=start;
return start;
}
void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.println(temp.info);
temp = temp.next;
}
}
void CheckForCircularLL(Node CircularLL)
{
Node slowPtr = CircularLL;
Node fastPtr = CircularLL;
while (slowPtr != null && fastPtr.next!=null)
{
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
if(slowPtr.info == fastPtr.info)
{
System.out.println("Link Linst is Circular");
System.exit(0);
}
}
System.out.println("Link Linst is NOT Circular");
}
}
public class CheckLinkListCircular
{
public static void main(String[] args)
{
Node ap = new Node(0);
System.out.println("Create Circular Linked List");
Node circularList = ap.createList();
System.out.println("Check whether Linked List is Circular : ");
System.out.println();
ap.CheckForCircularLL(circularList);
}
}
class Node
{
Node next;
int info;
Node(int data)
{
info = data;
next = null;
}
Node createList()
{
Node start = new Node(1);
Node mid1 = new Node(2);
Node mid2 = new Node(3);
Node mid3 = new Node(4);
Node end = new Node(5);
start.next=mid1;
mid1.next=mid2;
mid2.next=mid3;
mid3.next=end;
end.next=start;
return start;
}
void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.println(temp.info);
temp = temp.next;
}
}
void CheckForCircularLL(Node CircularLL)
{
Node slowPtr = CircularLL;
Node fastPtr = CircularLL;
while (slowPtr != null && fastPtr.next!=null)
{
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
if(slowPtr.info == fastPtr.info)
{
System.out.println("Link Linst is Circular");
System.exit(0);
}
}
System.out.println("Link Linst is NOT Circular");
}
}
public class CheckLinkListCircular
{
public static void main(String[] args)
{
Node ap = new Node(0);
System.out.println("Create Circular Linked List");
Node circularList = ap.createList();
System.out.println("Check whether Linked List is Circular : ");
System.out.println();
ap.CheckForCircularLL(circularList);
}
}
start two pointer from starting point of the list and increase 1st pointer by one and 2nd by two if the point meet on same point than the list is circular list else not.
- Amnish yadav December 19, 2014