446,227 Members | 1,491 Online
Need help? Post your question and get tips & solutions from a community of 446,227 IT Pros & Developers. It's quick & easy.

 P: 2 This was a question from GE interview when faced the GE interview.. Question : There is a one linked List with known starting and ending, you have to find out the middle of the linked list, you can traverse the whole linked list at once only.... Feb 19 '07 #1
6 Replies

 Expert 100+ P: 1,251 This was a question from GE interview when faced the GE interview.. Question : There is a one linked List with known starting and ending, you have to find out the middle of the linked list, you can traverse the whole linked list at once only.... That is easy, but unfortunately I don't think that we can give you the answer. It might be against policy. What do you other moderators think? Adrian Feb 19 '07 #2

 100+ P: 1,806 (Not that I'm a moderator....but) I can't see that there's any harm discussing the method........ The middle of a list is halfway from the start to the finish (obvious I know, but this is quite significant) I will assume that traversing the list once only means "you can only use one loop", not "you can only use one pointer" Step through the list: Pseudocode: Expand|Select|Wrap|Line Numbers counter == 0; this.element = first.element; mid.element=this.element; while(this.element != last.element) {    counter++;   if(counter % 2 == 0)   {     mid = mid.next();   }   this = this.next(); }   If there is 1 item, mid is correct, if there is an even number of items, thelater item is found, if there is an odd number, the middle is found (I think) Feb 19 '07 #3

 100+ P: 1,806 And I probably shouldn't have used "this".......so call it "current" if you like Feb 19 '07 #4

 P: 4 Hi, There is another solution for the same... Use 2 pointers p1 and p2, initially both should point to the head. Advance p1... one node at a time Advance p2... two node at a time. When p2 reaches the end, p1 is in the middle. Thanks Saby Abraham Feb 27 '07 #5

 P: 2 This was a question from GE interview when faced the GE interview.. Question : There is a one linked List with known starting and ending, you have to find out the middle of the linked list, you can traverse the whole linked list at once only.... Hi, i hope this works, because the starting and ending of the linked list is known one can traverse the list from either side, with a counter, thus same counter and the value at the pointer then break the loop. thus answer is out in 1/2 of the recurring loop with two pointers pointing either side of the linked list. Feb 27 '07 #6

 100+ P: 1,806 Assuming it's a doubly linked list you could take the "let's meet in (near) the middle). Knowing the start and end, however (even in a doubly linked list), doesn't help us to know how many elemetns are in between..... Feb 27 '07 #7