【出自WR笔试题】
难度系数：★★★☆☆ 被考察系数：★★★★★
题目描述：
找出单链表中的倒数第k个元素，例如给定单链表：1-＞2-＞3-＞4-＞5-＞6-＞7，则单链表的倒数第k=3个元素为5。
分析与解答：
方法一：顺序遍历两遍法
主要思路：首先遍历一遍单链表，求出整个单链表的长度n，然后把求倒数第k个元素转换为求顺数第n-k个元素，再去遍历一次单链表就可以得到结果。但是该方法需要对单链表进行两次遍历。
方法二：快慢指针法
由于单链表只能从头到尾依次访问链表的各个结点，因此，如果要找链表的倒数第k个元素，也只能从头到尾进行遍历查找，在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k步，然后两个指针同时往前移动。循环直到先行的指针值为null时，另一个指针所指的位置就是所要找的位置。程序代码如下：
程序的运行结果如下：
链表：1 2 3 4 5 6 7
链表倒数第3个元素为：5
算法性能分析：(www.xing528.com)
这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（N）。另外，由于只需要常量个指针变量来保存结点的地址信息，因此，空间复杂度为O（1）。
引申：如何将单链表向右旋转K个位置
题目描述：给定单链表1-＞2-＞3-＞4-＞5-＞6-＞7，k=3，那么旋转后的单链表变为5-＞6-＞7-＞1-＞2-＞3-＞4。
分析与解答：
主要思路：（1）首先找到链表倒数第k+1个结点slow和尾结点fast（如下图所示）。（2）把链表断开为两个子链表，其中，后半部分子链表结点的个数为k。（3）使原链表的尾结点指向链表的第一个结点。（4）使链表的头结点指向原链表倒数第k个结点。
实现代码如下：
程序的运行结果如下：
旋转前：1 2 3 4 5 6 7
旋转后：5 6 7 1 2 3 4
算法性能分析：
这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（n）。另外，由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O（1）。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
