View All num of num See all Photos Microsoft This employer has taken extra steps to respond to reviews and provide job seekers with accurate company information, photos, and reviews. Interested for your company?Learn More. www.microsoft.com Employer Engaged Overview Reviews Salaries Interviews Jobs Photos Benefits 9.3k Reviews 32k Salaries 4.0k Interviews Follow Add Review or Salary Follow Add Review or Salary Interview Question Software Development Engineer (SDE) Interview(Student Candidate) Redmond, WA Microsoft [Round 1] Find loop in a linked list Tags: See more , See less 8 Answer Add Tags Answer Interview Answer 3 Answers ▲ 0 ▼ Answer : If he means a boolean function to see if there is a loop in the linked list or not, then the answer is to use two pointers (slow and fast). "slow" walks one step every time and "fast" walks two step every time , if you reach null with fast pointer , then there is no loop , else if the fast and slaw pointer meet then there is a loop.if he means find the begin node of this loop (loop node), then you will write some extra code.you now get the node where "fast" and "slow" pointers meet in. then, arithmetically, the distance between that node and the "loop node" is equal to the distance between the head of the linked list and the "loop node". what we can do is after the slaw and fast pointers meet , fast pointer will point to the head of the linked list and both the slaw and the fast pointers will continue with speed equal to one step every time until they meet. the "loop node" is the node they met in. Mahmoud Wahdan on 2012-12-08 ▲ 0 ▼ There is a blog discussing this problem:http://codercareer.blogspot.com/2012/01/no-29-loop-in-list.htmlAdditionally, it's the 16th problem in the book <Coding Interviews: Questions. Analysis & Solutions>. You may get detailed analysis about this problem in the book. Harry on 2012-12-25 ▲ 0 ▼ C# Implementationhttp://arturodelosangeles.com/2015/01/27/find-loop-in-a-linked-list/ arturo on 2015-01-26 Add Answers or Comments To comment on this, Sign In or Sign Up.