牵着老婆满街逛

严以律己,宽以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

找出单向链表的倒数第m个元素

链表节点:
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)!
我太笨了,居然没有想到如此绝妙的算法.

posted on 2010-06-02 12:10 杨粼波 阅读(1068) 评论(7)  编辑 收藏 引用

评论

# re: 找出单向链表的倒数第m个元素[未登录] 2010-06-02 18:47 R

pFind = pFind->next;
// 间隔m个元素
pCurrent = pCurrent->next;
实际上是遍历两遍,时间复杂度和最简单的想法没有区别  回复  更多评论   

# re: 找出单向链表的倒数第m个元素 2010-06-02 19:30 杨粼波

@R
的确,这块代码算起来的确是遍历了两遍.
其实在空间上还可以节省掉一个临时变量的,那就是pFind,可以利用pHead,不过这样的话,阅读起来就会让人误解.  回复  更多评论   

# re: 找出单向链表的倒数第m个元素 2010-06-02 20:30 溪流

以前面试题做到过,当时不会,后来知道这个答案了也惊叹了一下。
现在看到楼上们说的,确实是两遍,跟最笨的方法——找到结尾回头找——相比,也根本好不到哪里去。。。学习了……  回复  更多评论   

# re: 找出单向链表的倒数第m个元素 2010-06-02 21:23 杨粼波

呵呵,我也是做的面试题.
还是这个算法比较符合我的理想中的美学.  回复  更多评论   

# re: 找出单向链表的倒数第m个元素 2010-06-10 10:35 imok

这个方法明显比那种遍历两次的方法要高效,而不是根本好不到哪里去  回复  更多评论   

# re: 找出单向链表的倒数第m个元素 2010-06-10 15:19 杨粼波

我把两种算法都放出来了,
这个一比较就很明白了.
第一个算法,需要循环链表两次.
第二个算法,只需要循环链表一次就足够了.

另外附上遍历的概念解释:
所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。  回复  更多评论   

# re: 找出单向链表的倒数第m个元素 2010-06-10 15:25 杨粼波

第二种算法,至少要少访问链表的节点m-1次.
可以直接去profile获取直观的时间损耗.  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理