鏈表節(jié)點(diǎn):
class Node
{
public:
int data;
Node* next;
public:
Node(int n) : data(n), next(0)
{
}
Node() : data(0), next(0)
{
}
Node* InsertAfter( int _data )
{
Node* newnode = new Node(_data);
newnode->next = next;
next = newnode;
return newnode;
}
};Node* FindMToLastNode(Node* pHead, int m)
{
// 第一次遍歷,獲取鏈表的計(jì)數(shù)
Node* pCurrent = pHead;
int nCount = 0;
while (pCurrent)
{
++nCount;
pCurrent = pCurrent->next;
}
// 防止越界
if (m > nCount) return 0;
// 第二遍遍歷,獲取倒數(shù)第m個節(jié)點(diǎn),也就是順數(shù)滴n個節(jié)點(diǎn)
int n = nCount - m + 1;
nCount = 0;
pCurrent = pHead;
while (pCurrent)
{
++nCount;
if (nCount == n)
{
return pCurrent;
}
pCurrent = pCurrent->next;
}
return 0;
}
這個算法很低效,要循環(huán)列表兩次,從時間上來說,消耗很大.從空間上,需要3個臨時變量,消耗也有點(diǎn)大.
高效的查找算法:
Node* FindMToLastNode(Node* pHead, int m)
{
// 查找到第m個元素
Node* pCurrent = pHead;
for (int i = 0; i < m; ++i)
{
if (pCurrent)
{
pCurrent = pCurrent->next;
}
else
{
return NULL;
}
}
// 一起繼續(xù)遍歷到鏈表尾部,
// 現(xiàn)在pFind和pCurrent之間間隔了m個元素,
// 所以,當(dāng)pCurrent遍歷到尾部的時候,
// pFind就到了倒數(shù)第m個元素的位置上.
Node* pFind = pHead;
while (pCurrent)
{
pFind = pFind->next;
// 間隔m個元素
pCurrent = pCurrent->next;
}
return pFind;
}
這個算法果然精妙!空間上只需要開銷兩個臨時變量,時間上只需要循環(huán)鏈表一遍,也就是O(n)!
我太笨了,居然沒有想到如此絕妙的算法.