ALLInterview.com :: Home Page KalAajKal.com
 Advertise your Business Here     
Browse  |   Placement Papers  |   Company  |   Code Snippets  |   Certifications  |   Visa Questions
Post Question  |   Post Answer  |   My Panel  |   Search  |   Articles  |   Topics  |   ERRORS new
   Refer this Site  Refer This Site to Your Friends  Site Map  Bookmark this Site  Set it as your HomePage  Contact Us     Login  |  Sign Up                      
info       Did you received any Funny E-Mails from your Friends and like to share with rest of our friends? Yeah!! you can post that stuff   HERE
Google
 
Categories  >>  Software  >>  Programming Languages  >>  C
 
 


 

 
 C interview questions  C Interview Questions
 C++ interview questions  C++ Interview Questions
 VC++ interview questions  VC++ Interview Questions
 Delphi interview questions  Delphi Interview Questions
 Programming Languages AllOther interview questions  Programming Languages AllOther Interview Questions
Question
How would you find a cycle in a linked list? 
 Question Submitted By :: Gvsk05
I also faced this Question!!     Rank Answer Posted By  
 
  Re: How would you find a cycle in a linked list?
Answer
# 1
Simultaneously go through the list by ones (slow iterator)
and by twos (fast iterator). If there is a loop the fast
iterator will go around that loop twice as fast as the slow
iterator. The fast iterator will lap the slow iterator
within a single pass through the cycle. Detecting a loop is
then just detecting that the slow iterator has been lapped
by the fast iterator.

This solution is "Floyd's Cycle-Finding Algorithm" as
published in "Non-deterministic Algorithms" by Robert W.
Floyd in 1967. It is also called "The Tortoise and the Hare
Algorithm"
 
Is This Answer Correct ?    0 Yes 1 No
Sujith
 
  Re: How would you find a cycle in a linked list?
Answer
# 2
The above method is working of course, but is not the most
efficient. Other methods are however quite complex and not
so easy to explain.
Anyway, to exemplify this aforementioned method, maybe not
the most efficient code, but off the top of my head, hope
there are no misspellings.

bool isCyclic(LinkedNode *list)
{
if(list == NULL || list->next == NULL) return false;
LinkedNode *node1 = list, *node2 = node1->next;
while(node1 != node2)
{
  if(node1==NULL || node2==NULL || node2->next == NULL)
return false;
  node1 = node1->next;
  node2= node2->next->next;
}
return true;
}

NOTE: the assumption is that for noncyclic list, the last
node has next pointer set to NULL.
 
Is This Answer Correct ?    0 Yes 1 No
Jaroosh
 
 
 

 
 
 
Other C Interview Questions
 
  Question Asked @ Answers
 
Tell about strtok & strstr functions Motorola2
There is a 100-story building and you are given two eggs. The eggs (and the building) have an interesting property that if you throw the egg from a floor number less than X, it will not break. And it will always brake if the floor number is equal or greater than X. Assuming that you can reuse the eggs which didn't broke; you got to find X in a minimal number of throws. Give an algorithm to find X in minimal number of throws.  2
which of the following statements is incorrect a.typedef struct new{ int n1; char n2; } DATA; b.typedef struct { int n3; char *n4; }ICE; c.typedef union { int n5; float n6; } UDT; d.#typedef union { int n7; float n8; } TUDAT; TCS5
consider the following structure: struct num nam{ int no; char name[25]; }; struct num nam n1[]={{12,"Fred"},{15,"Martin"},{8,"Peter"},{11,Nicholas"}}; ..... ..... printf("%d%d",n1[2],no,(*(n1 + 2),no) + 1); What does the above statement print? a.8,9 b.9,9 c.8,8 d.8,unpredictable value TCS2
Write a program to print this triangle: * ** * **** * ****** * ******** * ********** Don't use printf statements;use two nested loops instead. you will have to use braces around the body of the outer loop if it contains multiple statements.  1
what does the following function print? func(int i) { if(i%2)return 0; eale return 1; } main() { int =3; i=func(i); i=func(i); printf("%d",i);} TCS8
main() { int i=1; while (i<=5) { printf("%d",i); if (i>2) goto here; i++; } } fun() { here: printf("PP"); } ME3
6)swap(int x,y) { int temp; temp=x; x=y; y=temp; } main() { int x=2;y=3; swap(x,y); } after calling swap ,what are yhe values x&y?  2
Program to find the absolute value of given integer using Conditional Operators N-Tech2
What are the phases in s/w developed life cycle? wat is the diff b/w stack & queue...where do we use stack  5
Can we write a program without main() function?  6
34.what are bitwise shift operators? 35.what are bit fields? What is the use of bit fields in a structure declaration? 36.what is the size of an integer variable? 37.what are the files which are automatically opened when a c file is executed? 38.what is the little endian and big endian? 39.what is the use of fflush() function? 40.what is the difference between exit() and _exit() functions? 41.where does malloc() function get the memory? 42.what is the difference between malloc() and calloc() function? 43.what is the difference between postfix and prefix unary increment operators?  2
How would you find a cycle in a linked list?  2
What are .h files and what should I put in them?  3
int *p=20; if u print like dis printf("%d",p); o\p:- 20; how is it possible? plz give me the explanation. Global-Edge5
How to add two numbers without using arithmetic operators? Sapient7
what does exit() do? Cadence3
What's the difference between calloc() and malloc()?  2
52.write a “Hello World” program in “c” without using a semicolon? 53.Give a method to count the number of ones in a 32 bit number? 54.write a program that print itself even if the source file is deleted? 55.Given an unsigned integer, find if the number is power of 2?  4
Why doesn't the code "a[i] = i++;" work?  2
 
For more C Interview Questions Click Here 
 
 
 
 
 
   
Copyright Policy  |  Terms of Service  |  Help  |  Site Map 1  |  Articles  |  Site Map  |   Site Map  |  Contact Us interview questions urls   External Links 
   
Copyright © 2007  ALLInterview.com.  All Rights Reserved.

ALLInterview.com   ::  Forum9.com   ::  KalAajKal.com