Necessary and Sufficient

Question: How do you find the middle item in a list, or linked list without using the Count() property. This question is more common in C/C++ circles where linked lists are more prevalent and their use of pointers make things a touch more hairy for inexperienced developers.

Answer: In C#, List<T> and LinkedList<T> both implement IEnumerable<T>. Because of this we can write a generic function that operates on an IEnumerable<T> to handle both cases. So how to solve the problem? If IEnumerable <T> supported both forward and backward iteration, like a doubly linked list does, we could walk the list from both ends and they'd have to meet in the middle. Unfortunately we can't do that, enumerators in C# are effectively "fire hose cursors" - that is forward-only. Instead we can start two concurrent enumerations, one that steps forward 1 step at a time and one that steps forward 2 steps at a time. When the faster enumerator reaches the end of the list, the slower enumerator will be at the middle element. Note that this assumes that there aren't cycles in the list. Here's some C# code to do this.

        public static T ListMiddle<T>(IEnumerable<T> input)
        {
            if (input == null)
                return default(T);

            var slow = input.GetEnumerator();
            var fast = input.GetEnumerator();

            while (slow.MoveNext())
            {
                if (fast.MoveNext())
                {
                    if (!fast.MoveNext())
                        return slow.Current;
                }
                else
                {
                    return slow.Current;
                }
            }
            return slow.Current;
        }

And if C++ is your language you just need 2 pointers to the head of the single-linked list and you start a tortoise and hare race. When the hare (fast-moving pointer), which advances in 2-node steps, get to the end the tortoise (slowly-advancing pointer) will be at the middle - or thereabouts if the number of nodes is even. This assumes there are no cycles in the list. If there are an infinite loop results so we'd want to plug in loop-detection logic before pushing this to a live system! Here's some C++ code to demo this:

#include <stdio.h>
#include <stdafx.h>
#include <malloc.h>

struct node
{
    int data;
    node* next;
};

node* findMiddle(node* head)
{
    node* fast;
    node* slow;

    slow=fast=head;
    while(fast->next && fast->next->next)
    {
        fast=fast->next->next;
        slow=slow->next;
    }
    return slow;
}

int main()
{
    node* head= new node;
    node* second= new node;
    node* third= new node;

    head->data =1;
    head->next = second;

    second->data =2;
    second->next = third;

    third->data =3;
    third->next = NULL;

    node* mid=findMiddle(head);
    printf("Middle node is %d\n",mid->data);
}