链表节点:
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;
}
};
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) return0; // 第二遍遍历,获取倒数第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)!