下面两种方法原理相同。第二种更为直白一些。两个指针,同时从第一个节点出发,一个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; }