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。

分析与解答：

主要思路：①首先找到链表倒数第k+1个结点slow和尾结点fast（如下图所示）；②把链表断开为两个子链表，其中，后半部分子链表结点的个数为k；③使原链表的尾结点指向链表的第一个结点；④使链表的头结点指向原链表倒数第k个结点。

实现代码如下：

程序的运行结果为

算法性能分析：

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