链表节点:
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)
{
// 第一次遍历,获取链表的计数
Node* pCurrent = pHead;
int nCount = 0;
while (pCurrent)
{
++nCount;
pCurrent = pCurrent->next;
}
// 防止越界
if (m > nCount) return 0;
// 第二遍遍历,获取倒数第m个节点,也就是顺数滴n个节点
int n = nCount - m + 1;
nCount = 0;
pCurrent = pHead;
while (pCurrent)
{
++nCount;
if (nCount == n)
{
return pCurrent;
}
pCurrent = pCurrent->next;
}
return 0;
}
这个算法很低效,要循环列表两次,从时间上来说,消耗很大.从空间上,需要3个临时变量,消耗也有点大.
高效的查找算法:
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;
}
}
// 一起继续遍历到链表尾部,
// 现在pFind和pCurrent之间间隔了m个元素,
// 所以,当pCurrent遍历到尾部的时候,
// pFind就到了倒数第m个元素的位置上.
Node* pFind = pHead;
while (pCurrent)
{
pFind = pFind->next;
// 间隔m个元素
pCurrent = pCurrent->next;
}
return pFind;
}
这个算法果然精妙!空间上只需要开销两个临时变量,时间上只需要循环链表一遍,也就是O(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)
{ // 第一次遍历,获取链表的计数 Node* pCurrent = pHead; int nCount = 0; while (pCurrent) { ++nCount; pCurrent = pCurrent->next; } // 防止越界 if (m > nCount) return 0; // 第二遍遍历,获取倒数第m个节点,也就是顺数滴n个节点 int n = nCount - m + 1; nCount = 0; pCurrent = pHead; while (pCurrent) { ++nCount; if (nCount == n) { return pCurrent; } pCurrent = pCurrent->next; } return 0;}
高效的查找算法:
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; } } // 一起继续遍历到链表尾部, // 现在pFind和pCurrent之间间隔了m个元素, // 所以,当pCurrent遍历到尾部的时候, // pFind就到了倒数第m个元素的位置上. Node* pFind = pHead; while (pCurrent) { pFind = pFind->next; // 间隔m个元素 pCurrent = pCurrent->next; } return pFind;}
我太笨了,居然没有想到如此绝妙的算法.
