1.5 如何找出单链表中的倒数第k个元素

难度系数：★★★☆☆　被考察系数：★★★★☆

题目描述：

找出单链表中的倒数第 k 个元素，例如给定单链表：1-＞2-＞3-＞4-＞5-＞6-＞7，则单链表的倒数第k=3个元素为5。

分析与解答：

方法一：顺序遍历两遍

主要思路：首先遍历一遍单链表，求出整个单链表的长度 n，然后把求倒数第 k 个元素转换为求顺数第 n-k 个元素，再去遍历一次单链表就可以得到结果。但是该方法需要对单链表进行两次遍历。

方法二：快慢指针法

由于单链表只能从头到尾依次访问链表的各个结点，所以，如果要找链表的倒数第k 个元素，也只能从头到尾进行遍历查找，在查找过程中，设置两个指针，让其中一个指针比另一个指针先前移k步，然后两个指针同时往前移动。循环直到先行的指针值为null时，另一个指针所指的位置就是所要找的位置。程序代码如下：

程序的运行结果为

算法性能分析：

这种方法只需要对链表进行一次遍历，因此，时间复杂度为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个结点。

实现代码如下：

程序的运行结果为

算法性能分析：

这种方法只需要对链表进行一次遍历，因此，时间复杂度为O（n）。另外由于只需要几个指针变量来保存结点的地址信息，因此，空间复杂度为O（1）。