单链逆序寻找

单链逆序寻找

最近老是接触面试,接触了不少题。今天电话面试被问到了这么一题,当时没有给出最佳答案,过后在网上搜索了一下,发现果然还是有更简单的解决办法。(人还是这么懒,没有自己思考,罪过)

题目是:给你一个单链,要求找出倒数第M个元素。

直观的方法是:遍历一次得到元素总长N,再遍历一次第N-M个元素。

另一种改良方法是:遍历一次改单链为双链,再从尾部找到倒数第M个元素。

最佳的办法是:设置两个遍历指针,第一开始遍历并计数,当计数到第M个时,同时开始第二个遍历,当第一个到尾部时,第二个指向的即使倒数第M个元素。

我觉得在面试的时候出这种题目,如果事先没有接触过类似题目的人,能够答出的可能性不高。因为这种解答属于某种灵光一现的解决方案,即使答出来了,也不见得就是真正的想到了,也可能跟我一样是搜索到了类似题目。尽管如此,这道题目解决方法本身还是非常值得学习的,体现了解决问题时,利用了增加的办法,通常人都只想到用一个指针来遍历,如果增加一个,就能解决问题,和这个类似的问题还有寻找双链中的是死链。

Leave a Reply

Your email address will not be published. Required fields are marked *