One a not so standard way of doing that is while creating the link list, keep an extra pointer in the node to point to the jump location. Just hold the previous node in a temp say address of 2 node and when i/p reaches 4, point the jumper pointer to 4 and make 4 the next jumper pointer.
On Wed, Jul 20, 2011 at 7:27 PM, Ankur Khurana <ankur.kkhur...@gmail.com>wrote: > @Popli : Bingo , that is what i was thinking and mentioned in my previous > post...... > > > On Wed, Jul 20, 2011 at 7:08 PM, Gaurav Popli <abeygau...@gmail.com>wrote: > >> i want to ask one thing...the way some are saying first check with 2 >> then 4 and then 16....to reach at that place we are suppose to >> traverse it and also hav eto put a condition say like count<n or >> something...in this case also we are comparing so whats the >> use....correct me if im wrong..... >> >> On Wed, Jul 20, 2011 at 6:58 PM, bittu <shashank7andr...@gmail.com> >> wrote: >> > can be done in O(n) find tow nodes from starting position find two >> > nodes p,q such that p < k & k < q as linked list is sorted we have to >> > keep going on in right direction complexity will no less then O(N) as >> > its linked list there is no notion of binary search sorted linked list >> > think out why ? >> > >> > only think we can apply some logic to reduce the comparisons that's i >> > also think will be gr8 improvement but approach sounds good if start >> > comparing the nodes value using multiple of 2 fact .e.g. take an >> > integer i=2^j & from j=0 to start comparing 2^0th node, 2^1th node, >> > 2^2th node....2^jth node might be we are able to reduce the number of >> > comparisons >> > >> > do notify me via gmail if i am wrong if u find difficulty in TC ? else >> > happy learning >> > >> > if this would have been sorted array then we could have been solved it >> > O(logn) suing same approach. >> > >> > >> > Thanks >> > Shashank Mani >> > Computer Science >> > Birla Institute of Technology, Mesra >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups "Algorithm Geeks" group. >> > To post to this group, send email to algogeeks@googlegroups.com. >> > To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> > For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > >> > >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Ankur Khurana > Computer Science , 4th year > Netaji Subhas Institute Of Technology > Delhi. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
