Amazon Interview Question
Country: India
Interview Type: Written Test
While iterating slow and false pointers, they will meet at a place and we'll know that loop is there as explained above. Freeze one pointer there and and again make the other pointer to point at the head. Now iterate both pointers one-one step. They will meet again and that will be the starting point. No need to find the length of the the loop !!!
public void cyclicTest(Node node){
int num=0;
Node head=node;
if(node==null){
System.out.println("No Nodes: 0");
return;
}
while(node.next!=null){
num++;
node=node.next;
if(head==node){
System.out.println("Cyclic:"+ num);
return;
}
}
System.out.println("ACyclic:"+ (num+1));
}
////////////////////////////////////////////////
O(n) to compute cyclic or acyclic
fast = slow = headbackup = head;
count = 0;
do
{
if( fast->next != NULL )
fast = fast->next->next;
count = count + 2;
else
return ++count;
slow = slow->next
}while( slow != fast );
// the point at which slow and fast meet will be at the same distance from the start of the loop as the distance between head and start of the loop
// count the length of the LL segment that is not in the loop
count = 0;
while( headbackup != slow )
count++;
headbackup = headbackup->next;
slow = slow->next;
// count the length of the LL segment that is in the loop
do
{
count++;
slow = slow->next;
while( slow != headbackup );
suppose x = distance from head to cycle start
y = distance from meeting point back to cycle star
then
x = y + n* cycle_length (n is integer, it means faster pointer might loop multiple times before meet slow pointer)
but your algorithem still work.
here is the prove
let k = distance from cycle start to meeting point
2 * (x+k) = x + k + y +k + n*cycle_length
y+k = cycle_length (faster pointer move at least one cycle)
which reduce to
x = y + n * cycle_length
I proved it this way:
N -> number of steps the slower node made in the loop before meeting the faster
L -> length of the loop
k -> number of steps faster was ahead of slower when the slower entered the loop(offset)
When the pointers met, they were at the same displacement(hence the %) from the beginning of the loop.
(2N+k)%L = N%L
2N+k-LQ1 = N-LQ2
N = L(Q1-Q2)-k
N is a multiple of L -> both pointers met at the starting point
-k -> k steps before the starting point
Here is a solution I think will work: have used slow and fast pointer to find the loop first then to count the number of nodes.
public int nodeCount(LinkedLists node){
LinkedLists slow=head;
LinkedLists fast=head;
while(fast!=null && fast.next!=null) {
slow = slow.next;
fast = fast.next.next;
if(slow==fast) //both pointers have collided
break;
}
//Check if there are no loops at all
if(fast==null || fast.next==null)
return 0;
// Now move slow to head, and increment slow and fast by one step so that they meet at the loop/cycle beginning point.
slow = head;
int countk = 0;
while(slow!=fast) {
slow = slow.next;
fast = fast.next;
countk++;
}
//Now keep the slow pointer there and increment fast pointer by 1, when slow==fast u have counted the entire list
fast = fast.next;
countk++;
while(slow!=fast) {
fast = fast.next;
countk++;
}
return countk;
}
This is my solution
#include <stdio.h>
#include <stdlib.h>
typedef struct __LinkedListNode__ {
int data;
struct __LinkedListNode__* next;
} LinkedListNode;
int count(LinkedListNode* head) {
LinkedListNode* sp = head; //slow pointer
LinkedListNode* fp = head; //fast pointer
LinkedListNode* p = head; //follow up pointer
int count = 0;
if (head == NULL)
return count;
//Jump slow pointer once and fast pointer twice
//till they meet if there is a cycle or if it terminates with NULL
do {
if (sp->next) {
sp = sp->next;
count++;
}
if (fp->next) {
if (fp->next->next)
fp = fp->next->next;
else
fp = fp->next; //ensures sp and fp meets if NULL encountered at end
}
} while (sp != fp);
//no cycle. return count = slow jumps + 1
if (sp->next == NULL)
return count + 1;
// Cycle begins from the head, return the slow jumps
if (p == sp)
return count;
//Move followup pointer and fast pointer by one jump until they meet
// This is the cycle head
while (p != fp) {
fp = fp->next;
p = p->next;
}
//Move slow pointer till it meets the cycle head and return the count
do {
sp = sp->next;
count++;
} while (sp != p);
return count;
}
void insert_at_beginning(LinkedListNode** head, int data) {
if (*head == NULL) {
*head = malloc(sizeof(LinkedListNode));
(*head)->data = data;
(*head)->next = NULL;
} else {
LinkedListNode* node = malloc(sizeof(LinkedListNode));
node->data = data;
node->next = *head;
*head = node;
}
}
void destroy(LinkedListNode* head) {
LinkedListNode* node;
while (head) {
node = head;
head = head->next;
free(head);
}
}
int main() {
LinkedListNode* head = NULL;
LinkedListNode* tail = NULL;
LinkedListNode* cycle_head = NULL;
insert_at_beginning(&head, 10);
tail = head;
insert_at_beginning(&head, 9);
insert_at_beginning(&head, 8);
insert_at_beginning(&head, 7);
insert_at_beginning(&head, 6);
cycle_head = head;
insert_at_beginning(&head, 5);
insert_at_beginning(&head, 4);
insert_at_beginning(&head, 3);
insert_at_beginning(&head, 2);
insert_at_beginning(&head, 1);
//Create a cycle
tail->next = cycle_head;
printf("count:%d\n",count(head));
//Remove cycle for destruction
tail->next = NULL;
destroy(head);
}
Here fp will reach earlier than sp to NULL when it is acyclic. So in that case if (fp->next) may give the exception. because fp points to NULL and tries to access the next.
//till they meet if there is a cycle or if it terminates with NULL
do {
if (sp->next) {
sp = sp->next;
count++;
}
if (fp->next) {
if (fp->next->next)
fp = fp->next->next;
else
fp = fp->next; //ensures sp and fp meets if NULL encountered at end
}
} while (sp != fp);
First check for cyclic or acyclic using slow and fast pointer.
- Anonymous February 19, 2012If acyclic then it's easy to find out
If cyclic.
by help of slow and fast pointer find the no of nodes in loop.
let's say no of nodes in loop is L1
then start from head keep two pointer p1 and p2
move P2, L1 step ahead of P1 and then start moving them together and keep the counter with P1 once the collide u r the beginning of loop by the time counter will have value equal to linear link let's say L2
return L1 +L2