Vamsi Pavan’s Place

When curiousity outbursts …..

Detect cycle in a linked list

October 6th, 2006 · No Comments · Algorithms

ptr1 = ptr2 = head;
do{
ptr1 = ptr1 -> next;
ptr2 = ptr2 -> next -> next;
}while(ptr1 != ptr2);

ptr2 is iterating along the list with double the speed of ptr1. If there is any cycle, then ptr1 and ptr2 will loop in the list. And since ptr1 is moving at one step and ptr2 is moving faster than ptr1 they will at some point meet.

Middle element in a list
Using the same logic of one slow pointer and one fast pointer, we can detect the middle of a list also.
Kth element from the last in a list
Median of an array can also be done in the same way as Kth least element

Bookmark it! These icons link to social bookmarking sites where readers can share and discover new web pages.
  • bodytext
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google
  • Live
  • StumbleUpon
  • BlinkList
  • YahooMyWeb
  • NewsVine
  • blogtercimlap
  • Netvouz
  • Technorati
  • Slashdot
  • Print this article!

Tags:

0 responses so far ↓

  • There are no comments yet...Kick things off by filling out the form below.

Leave a Comment