只遍历一次单链表，确定单链表中间节点的位置
问题：给定一个单链表，不知道节点N的值，怎样只变量一次就知道中间节点？#include "stdafx.h"
#include <iostream>
using namespace std;
structTNode
{
int nValue;
TNode*pNext;
TNode()
{
nValue= 0;
pNext= NULL;
}
};
TNode* CreateList(int* nArray, intnLen)
{
TNode*pHead = new TNode();
TNode*pCur = NULL;
TNode*pPre = pHead;
for(int i=0;i<nLen; ++i)
{
pCur= new TNode();
pCur->nValue= nArray[i];
pPre->pNext= pCur;
pPre= pCur;
}
return pHead;
}
voidPrintList(TNode*& pHead)
{
if(NULL == pHead || NULL == pHead->pNext)
{
cout<<"列表为空"<<endl;
return;
}
TNode*p = pHead->pNext;
while(NULL != p)
{
cout<<p->nValue<<endl;
p= p->pNext;
}
}
boolFindMiddleValue(TNode* pHead,int& nValue)
{
if(NULL == pHead || NULL == pHead->pNext)
{
return false;
}
TNode*p = NULL;
TNode*q = NULL;
p= pHead->pNext;
q= pHead->pNext;
while(NULL != q)
{
q= q->pNext;
if(NULL == q)
{
break;
}
q= q->pNext;
if(NULL == q)
{
break;
}
p= p->pNext;
}
nValue= p->nValue;
return true;
}
int_tmain(int argc, _TCHAR* argv[])
{
int nLen = 7;
int nArray[] = {5,14,3,12,1,8,10}; //{3,5,1};//
TNode*pHead = CreateList(nArray,nLen);
cout<<"原始链表中的内容:"<<endl;
PrintList(pHead);
int nValue;
if(!FindMiddleValue(pHead,nValue))
{
cout<<"没有找到"<<endl;
}
cout<<"找到的中间节点为:"<<nValue<<endl;
return 0;
}
执行结果：
基本思想：设立两个指针，比如*p和*q。p每次移动两个位置，而q每次移动一个位置，当p到达最后一个节点时，q就是中间节点了。
补充：综合编程 , 其他综合 ,
