By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,227 Members | 1,491 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,227 IT Pros & Developers. It's quick & easy.

Linked List

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
Share this Question
Share on Google+
6 Replies


AdrianH
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

DeMan
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
  1. counter == 0;
  2. this.element = first.element;
  3. mid.element=this.element;
  4. while(this.element != last.element)
  5. {
  6.    counter++;
  7.   if(counter % 2 == 0)
  8.   {
  9.     mid = mid.next();
  10.   }
  11.   this = this.next();
  12. }
  13.  
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

DeMan
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

DeMan
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

Post your reply

Sign in to post your reply or Sign up for a free account.