// middle value of a linked list example
// does not have any error-checking

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

void add(Node** h, int d) // add to front of list
{
Node* n;
n = (Node*) malloc(sizeof(Node));
n->data = d;
n->next = *h;
*h = n;
}

void display(Node* h)
{
Node* p = h;
while (p != NULL)
{
printf(”%d -> “, p->data);
p = p->next;
}
printf(”X\n”);
}

int size(Node* h)
{
Node* p = h;
int ct = 0;
while (p != NULL) {
++ct;
p = p-> next;
}
return ct;
}

int midValue(Node* h)
{
Node* p = h;
for (int ct = 1; ct < size(h)/2; ++ct)
p = p->next;

return p->next->data;
}

int midValueFancy(Node *h)
{
Node* p = h; // advances once
Node* q = h; // advances twice
while (q->next != NULL && q->next->next != NULL)
{
p = p->next;
q = q->next;
q = q->next;
}
return p->data;
}

int _tmain(int argc, _TCHAR* argv[])
{
char dummy;
Node* head;

printf(”%s”, “Begin linked list mid value demo\n”);
head = NULL;
add(&head, 10);
add(&head, 8);
add(&head, 6);
add(&head, 4);
add(&head, 2);
printf(”List is:\n”);
display(head);
printf(”List has size %d\n”, size(head));
printf(”The middle value is %d\n”, midValueFancy(head));

scanf(”%c”, &dummy);
return 0;
}