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

【出自WR笔试题】

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

题目描述：

找出单链表中的倒数第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）。