推荐订阅源

    今天在csdn上看到一道面试题。觉得很有意思。

原帖见 http://topic.csdn.net/u/20100408/19/f8c04daa-67b9-407c-afa7-f1c731bf9aa5.html

    坛子上基本上给了两种方案。

   1.先遍历一遍。得到链表的长度，然后在遍历一次（l-n）。就能得到第倒数n个结点了。

   2.设置两个指针，p1，p2，p1先跑出去n个节点，然后p1，p2一起跑，等p1到头了，p2就是目标结点了。 

设计的很巧妙。但是实际上也是几乎对链表遍历了2次。

   这里提一个在方案2的基础上进行优化的算法。

   2个指针，p1，p2  ，p1先跑出去n个结点，使用一个临时变量 pTmp 记录下当前的位置，然后p1继续向前跑n个结点 。这时候会有两种情况。

• A. p1还没跑完n个结点，链表就到头了。这时候 p1回到 pTmp的位置，然后使用 方案2.就能得到倒数第n个结点。
• B. p1跑了n个结点，链表没到头。这个时候，将p2的值设置为pTmp的值，然后更新pTmp的值为p1，p1一直往下跑。等p1跑到跟 A情况一样的时候，使用A的方案。就能得到结果了。 采用这种方案，几乎只用将链表遍历一遍就能得到想要的结果。

不知道我说的清不清楚。呵呵，给了思路，就不给相关的代码。

 ----------------------------------------------------------------------

补充下，我的这个方案还有可以优化的余地。就是 p1在向前跑的时候对n的处理。可以加入动态预测的机制，第一次n没到头，第2次直接跑2n个结点看怎么样。然后在加入回退的考虑，简单的思路，没具体去实现，对超长链表效率会得到改善。算法的优化核心就在于减少p2访问结点的次数，让p2以跳跃的方式前进。

不知道有没有时间复杂度小于 n 的算法，上面的几种方案来看，链表的一次遍历是怎么也跑不了了。