Algorithm in C# : How to find middle element of linked list in one pass?

One of the most popular question from data structures and algorithm, mostly asked on telephonic interview. Since many programmer know that, in order to find length of linked list we need to first traverse through linked list till we find last node, which is pointing to null, and then in second pass we can find middle element by traversing only half of length. They get confused when interviewer ask him to do same job in one pass. In order to find middle element of linked list in one pass you need to maintain two pointer, one increment at each node while other increments after two nodes at a time, by having this arrangement, when first pointer reaches end, second pointer will point to middle element of linked list.

Below is the structure of linked list

gdprZ[1]

To solve this problem with C#, first we need to make a linked list.

Define a simple class which has three attributes: Name, Pre and Next, Name is only for identifying, the Pre and Next point to its previous and next item.

 

 

Tagged with: ,
Posted in Algorithm, C#
0 comments on “Algorithm in C# : How to find middle element of linked list in one pass?
1 Pings/Trackbacks for "Algorithm in C# : How to find middle element of linked list in one pass?"
  1. […] is another frequently asked linked list interview question. This question is exactly similar to finding middle element of linked list in single pass. If we apply same trick of maintaining two pointers and increment other pointer, when first has […]

Categories

Related Posts