Kotlin面试算法：链表相邻元素翻转

【出自TX笔试题】

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

题目描述：

把链表相邻元素翻转，例如给定链表为1-＞2-＞3-＞4-＞5-＞6-＞7，则翻转后的链表变为2-＞1-＞4-＞3-＞6-＞5-＞7。

分析与解答：

方法一：交换值法

最容易想到的方法就是交换相邻两个结点的数据域，这种方法由于不需要重新调整链表的结构，因此，比较容易实现，但是这种方法并不是考官所期望的解法。

方法二：就地逆序

主要思路：通过调整结点指针域的指向来直接调换相邻的两个结点。如果单链表恰好有偶数个结点，那么只需要将奇偶结点对调即可，如果链表有奇数个结点，那么只需要将除最后一个结点外的其他结点进行奇偶对调即可。为了便于理解，下图给出了其中第一对结点对调的方法。(www.xing528.com)

在上图中，当前遍历到结点cur，通过（1）～（6）6个步骤用虚线的指针来代替实线的指针实现相邻结点的逆序。其中，（1）～（4）实现了前两个结点的逆序操作，（5）和（6）两个步骤向后移动指针，接着可以采用同样的方式实现后面两个相邻结点的逆序操作。实现代码如下：

程序的运行结果如下：

顺序输出：1 2 3 4 5 6 7

逆序输出：2 1 4 3 6 5 7

上例中，由于链表有奇数个结点，因此，链表前三对结点相互交换，而最后一个结点保持在原来的位置。

算法性能分析：

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