问题：
一个单链表,长度未知,如何快速的找出位于中间的那个元素？
设置两个指针，p1,p2, 开始p1,p2均位于链接的头部。
p1 每次步进两步，
p2 每次步进一步
当p1到达链表的末尾时，p2所在的位置就是链表的中间元素
时间复杂度为O(n)
详细情况请见代码：
#include <iostream>
using namespace std;
struct node{
node *next;
int data;
};
//用一个类封装链表的操作
class linknode{
public:
linknode(){
head = new node;
head->next = NULL;
}
~linknode(){
delete head;
}
//销毁所有资源
void Clear(){
node *p,*q;
p = head;
while(p){
q = p->next;
delete p;
p = q;
}
//注意这里
head->next = NULL;
cout << "OK,destroyed all elements" << endl;
}
//尾插法
void Create(int n){
node *p,*q;
int data;
p = head;
while(n--){
q = new node;
cout << "input data:";
cin >> data;
q->data = data;
q->next = NULL;
p->next = q;
p = q;
}
}
void Output(){
node *p;
//注意，不要写成p = head;因为头结点没有保存数据
p = head->next;
while(p){
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//查找中间的元素
node* findMid(){
node *p1,*p2;
p1 = head;
p2 = head;
while(p1 != NULL && p2 != NULL){
p1 = p1->next->next;
p2 = p2->next;
}
return p2;
}
private:
node *head;
};
int main(){
linknode lk;
node *tmp;
lk.Create(5);
lk.Output();
tmp = lk.findMid();
cout << tmp->data << endl;
lk.Clear();
}