只遍历链表一次求链表中间结点

ListNode* MidNode( ListNode* pHead )
{
if ( NULL == pHead )
return NULL;
else if ( NULL == pHead->m_pNext )
return pHead;
else if ( NULL == pHead->m_pNext->m_pNext )
return pHead;

ListNode* pFast = pHead;
ListNode* pSlow = pHead;

while ( NULL != pFast->m_pNext/*最后一个结点*/ ){
if ( NULL == pFast->m_pNext->m_pNext )//pFast->m_pNext不可能为NULL. 所以我们不必担心NULL->m_pNext情况发生
break;

pFast = pFast->m_pNext->m_pNext;
pSlow = pSlow->m_pNext;
}

return pSlow;
}

测试代码:

//求链表的中间节点，链表中元素个数为奇数返回中间节点，偶数返回中间结点中任一个(这里返回第一个)
#include <iostream>
using namespace std;


struct ListNode{
int m_nKey;
ListNode* m_pNext;

ListNode( ListNode* pNext, int value )
: m_pNext( pNext )
, m_nKey( value )
{}
};


ListNode* MidNode( ListNode* pHead );
void push_back( ListNode** pHead, int value );


int main( )
{
ListNode* pHead = NULL;
//push_back( &pHead, 1 );
//push_back( &pHead, 2 );
//push_back( &pHead, 3 );

//push_back( &pHead, 1 );

//push_back( &pHead, 1 );
//push_back( &pHead, 2 );

push_back( &pHead, 1 );
push_back( &pHead, 2 );
push_back( &pHead, 3 );
push_back( &pHead, 4 );


cout << MidNode( pHead )->m_nKey << endl;

return 0;
}


void push_back( ListNode** pHead, int value )
{
if ( NULL == pHead )
return;

ListNode* pNewNode = new ListNode( NULL, value );

if ( NULL == *pHead ){
*pHead = pNewNode;
return;
}

ListNode* pNode = *pHead;

while ( NULL != pNode->m_pNext )
pNode = pNode->m_pNext;

pNode->m_pNext = pNewNode;
}

//我们不用那种 遍历一遍得出链表个数，再找中间结点的需要遍历链表两次的方法，我们用只遍历链表一次就得出中间结点方法
//我们利用两个指针，pFast和pSlow:快指针一次走两步，慢指针一次走一步。
//当快指针到达链表结尾或链表倒数第二个结点时(分别对应链表结点个数为奇数和偶数)，慢指针到达链表最中间(奇数)或中间两个结点的前一个结点(偶数)
//我们把 链表为空， 链表只有一个结点，和链表有两个结点的情况单独拿出来处理.
ListNode* MidNode( ListNode* pHead )
{
if ( NULL == pHead )
return NULL;
else if ( NULL == pHead->m_pNext )
return pHead;
else if ( NULL == pHead->m_pNext->m_pNext )
return pHead;

ListNode* pFast = pHead;
ListNode* pSlow = pHead;

while ( NULL != pFast->m_pNext/*最后一个结点*/ ){
if ( NULL == pFast->m_pNext->m_pNext )//pFast->m_pNext不可能为NULL. 所以我们不必担心NULL->m_pNext情况发生
break;

pFast = pFast->m_pNext->m_pNext;
pSlow = pSlow->m_pNext;
}

return pSlow;
}