GeekInterview.com
Series: Subject: Topic:
Question: 26 of 51

Finding a 'circle' in a linked list

You have n numbrer Node objects - could be 1,000,000 for all you know. Each Node has a getNext() method that returns the next Node (a linked list).

But the chain of n number of Node objects linked together by the getNext() method, somewhere in the chain, points back to a Node earlier in the chain so if you keep calling getNext() to walk the chain you will never get to the last Node - it will loop forever.

What is the best way to determine if this linked list of Node objects has a 'circle' and extra points if you can tell where in the chain does it occur i.e. what is the Node that is returing an earlier Node in the chain?

Asked by: wcmaggot | Member Since Jun-2009 | Asked on: Jun 8th, 2009

View all questions by wcmaggot

Showing Answers 1 - 2 of 2 Answers
doddaiah

Answered On : Jun 21st, 2009

View all answers by doddaiah

Take two pointers P1 and P2.


Initially let P1 and P2 point to starting node (S) and set counter to zero.
increment the counter
then check 
while(1) {

if p1 == p2 ->next
{
   print the counter value this is the node where circle starts.
   exit();
}

else {
    increment the counter; 
    p1 = p2;
    p2 = p2->next;
    if ( S == p2 )
    exit(); if Staring node is equal to P2 then we have reached end of list. 
}

}

Yes  1 User has rated as useful.
  
Login to rate this answer.
kaushurtz

Answered On : Mar 2nd, 2010

View all answers by kaushurtz

There are many ways to find loops in linked list but the best one is known as tortoise and hare algorithm.
In this we take 2 nodes say slow and fast node. Then we move the slow node by one shift ie startNode.next and the fast node with 2 shifts and then compare both slow and fast node. If they come to be equal at any time while iteration then this indicates that the linked list has a loop.

  
Login to rate this answer.

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

Related Answered Questions

Related Open Questions

User Panel

Register
Login
Lost Password
Get Activation Code

Categories

Algorithms

ColdFusion

Computer Awareness

Delphi

Perl

PHP

Python

VBA

VoiceXML

XML

Interview Coaching

How do you approach a problem?

Careers and Higher Education Options for BBA Graduates

How to handle academic gap while applying for a job?

Does a problem make you a better person?

How do you handle difficult situations?

What was the most important decision you ever had to make?

Have you gone above and beyond your job description?

Describe a time when you had to listen to someone.

Has there been a time when you were presented a problem and solved it?

What do you do when someone criticizes you?

Ads

Connect

twitter fb Linkedin GPlus RSS

Ads

Interview Question

 Ask Interview Question?

 

Latest Questions

Interview & Career Tips

Get invaluable Interview and Career Tips delivered directly to your inbox. Get your news alert set up today, Once you confirm your Email subscription, you will be able to download Job Inteview Questions Ebook . Please contact me if you there is any issue with the download.

Subscribe