下面两种方法原理相同。第二种更为直白一些。两个指针，同时从第一个节点出发，一个P走一步，一个Q走两步。当第二个指针走到末尾节点，当前节点为中值（此处未处理偶数节点是输出中间两个节点。这里只要统计走过的节点个数为奇数还是偶数。）

这种方法还可以在O（ n ) 的时间复杂度判断链表是否成环

#include <iostream>
using namespace std;
typedef struct node{
    int data;
    node *next;
}node;
 
node *Create(){
    node *head = new node;
    node *p;
    head -> data = 0;
    for( int i = 0; i < 10; ++i ){
        node *q = new node;
        q -> data = i;
        if( head -> data == 0 ){
            head -> next = q;
        }
        else{
            p -> next = q;
        }
        p = q;
        head -> data++;
    }
    p -> next = NULL;
    return head;
}
 
 
void Print( node *head ){
    node *p = head -> next;
    while( p != NULL ){
        cout << p -> data <<endl;
        p = p -> next;
    }
}
 
node *SeachTheMid( node *head ){
    node *p = NULL, *q = NULL;
    int i = 0, j = 0;
    p = q = head -> next;
    while( p != NULL ){
        if( i > 2 * j ){
            j++;
            q = q -> next;
        }
        i++;
        p = p -> next;
    }
    return q;
}
 
node *SeachTheMid1( node *head ){
    node *p = NULL, *q = NULL;
    p = q = head -> next;
    while( q -> next != NULL ){
        if( p -> next != NULL )
            p = p -> next;
        else
            break;
        if( q -> next -> next != NULL )
            q = q -> next -> next;
        else
            break;
    }
    return p;
}
 
int main()
{
    node *head = Create();
    Print( head );
    node *Head = SeachTheMid( head );
    Head = SeachTheMid1( head );
    cout << Head -> data;
    return 0;
}