publicstaticvoidmain(String[] args) { LinkedList linkedList = new LinkedList(); int[] arr = {4,3,2,1}; for (int i = 0; i < arr.length; i++) { linkedList.addNode(arr[i]); } Node newHead = linkedList.invertLinkedList(linkedList.head.next); // 翻转后别忘了设置头结点的后继结点！ linkedList.head.next = newHead; linkedList.printList(); // 打印 1，2，3，4 }
画外音：翻转后由于 head 的后继结点变了，别忘了重新设置哦！
4、计算时间/空间复杂度
由于递归调用了 n 次 invertLinkedList 函数，所以时间复杂度显然是 O(n), 空间复杂度呢，没有用到额外的空间，但是由于递归调用了 n 次 invertLinkedList 函数，压了 n 次栈，所以空间复杂度也是 O(n)。
递归一定要从函数的功能去理解，从函数的功能看，定义的递归函数清晰易懂，定义好了之后，由于问题与被拆分的子问题具有相同的解决思路，所以子问题只要持续调用定义好的功能函数即可，切勿层层展开子问题，此乃递归常见的陷阱！仔细看函数的功能，其实就是按照下图实现的。
(对照着代码看，是不是清晰易懂^_^)
非递归翻转链表
（迭代解法）
我们知道递归比较容易造成栈溢出，所以如果有其他时间/空间复杂度相近或更好的算法，应该优先选择非递归的解法,那我们看看如何用迭代来翻转链表，主要思路如下
步骤 1：
定义两个节点：pre, cur ，其中 cur 是 pre 的后继结点，如果是首次定义， 需要把 pre 指向 cur 的指针去掉，否则由于之后链表翻转，cur 会指向 pre， 就进行了一个环
(如下)
，这一点需要注意
步骤2：
知道了 cur 和 pre,翻转就容易了，把 cur 指向 pre 即可，之后把 cur 设置为 pre ，cur 的后继结点设置为 cur 一直往前重复此步骤即可,完整动图如下
注意：同递归翻转一样，迭代翻转完了之后 head 的后继结点从 4 变成了 1，记得重新设置一下。
知道了解题思路，实现代码就容易多了，直接上代码
/** * 迭代翻转 */ publicvoiditerationInvertLinkedList() { // 步骤 1 Node pre = head.next; Node cur = pre.next; pre.next = null;
while (cur != null) { /** * 务必注意：在 cur 指向 pre 之前一定要先保留 cur 的后继结点，不然 cur 指向 pre 后就再也找不到后继结点了 * 也就无法对 cur 后继之后的结点进行翻转了 */ Node next = cur.next; cur.next = pre; pre = cur; cur = next; } // 此时 pre 为头结点的后继结点 head.next = pre; }
用迭代的思路来做由于循环了 n 次，显然时间复杂度为 O(n),另外由于没有额外的空间使用，也未像递归那样调用递归函数不断压栈，所以空间复杂度是 O(1),对比递归，显然应该使用迭代的方式来处理！
花了这么大的精力我们总算把翻转链表给搞懂了，如果大家看了之后几道翻转链表的变形，会发现我们花了这么大篇幅讲解翻转链表是值得的。
接下来我们来看看链表翻转的变形
变形题 1：给定一个链表的头结点 head,以及两个整数 from 和 to ,在链表上把第 from 个节点和第 to 个节点这一部分进行翻转。例如：给定如下链表，from = 2, to = 4
head-->5-->4-->3-->2-->1
将其翻转后，链表变成
head-->5--->2-->3-->4-->1
有了之前翻转整个链表的解题思路，现在要翻转部分链表就相对简单多了,主要步骤如下:
1. 根据 from 和 to 找到 from-1, from, to, to+1 四个结点(注意临界条件，如果 from 从头结点开始，则 from-1 结点为空, 翻转后需要把 to 设置为头结点的后继结点， from 和 to 结点也可能超过尾结点,这两种情况不符合条件不翻转)。
2. 对 from 到 to 的结点进行翻转。
3. 将 from-1 节点指向 to 结点，将 from 结点指向 to + 1 结点。
知道了以上的思路，代码就简单了,按上面的步骤1，2，3 实现，注释也写得很详细，看以下代码
（对 from 到 to 结点的翻转我们使用迭代翻转，当然使用递归也是可以的，限于篇幅关系不展开，大家可以尝试一下）
。
/** * 迭代翻转 from 到 to 的结点 */ publicvoiditerationInvertLinkedList(int fromIndex, int toIndex) throws Exception {
Node fromPre = null; // from-1结点 Node from = null; // from 结点 Node to = null; // to 结点 Node toNext = null; // to+1 结点
时间复杂度是多少呢，对链表从头到尾循环了 n 次，同时每 k 个结点翻转一次，可以认为总共翻转了 n 次，所以时间复杂度是O(2n),去掉常数项，即为 O(n)。注：这题时间复杂度比较误认为是O(k * n),实际上并不是每一次链表的循环都会翻转链表，只是在循环链表元素每 k 个结点的时候才会翻转。
变形3: 变形 2 针对的是顺序的 k 个一组翻转，那如何逆序 k 个一组进行翻转呢
例如：给定如下链表，
head-->1-->2-->3-->4-->5
逆序 k 个一组翻转后，
链表变成（k = 2 时）
head-->1--->3-->2-->5-->4
这道题是字节跳动的面试题，确实够变态的，顺序 k 个一组翻转都已经属于 hard 级别了，逆序 k 个一组翻转更是属于 super hard 级别了，不过其实有了之前知识的铺垫，应该不难，只是稍微变形了一下，只要对链表做如下变形即可
代码的每一步其实都是用了我们之前实现好的函数，所以我们之前做的每一步都是有伏笔的哦！就是为了解决字节跳动这道终极面试题！
/** * 逆序每 k 个一组翻转链表 * @param k */ publicvoidreverseIterationInvertLinkedListEveryK(int k) { // 先翻转链表 iterationInvertLinkedList(); // k 个一组翻转链表 iterationInvertLinkedListEveryK(k); // 再次翻转链表 iterationInvertLinkedList(); }
输入一个链表，输出该链表中的倒数第 k 个结点。比如链表为 head-->1-->2-->3-->4-->5。求倒数第三个结点（即值为 3 的节点）
分析：我们知道如果要求顺序的第 k 个结点还是比较简单的，从 head 开始遍历 k 次即可，如果要求逆序的第 k 个结点，常规的做法是先顺序遍历一遍链表，拿到链表长度，然后再遍历 链表长度-k 次即可，这样要遍历两次链表，不是那么高效，如何只遍历一次呢，还是用我们的说的快慢指针解法
• 首先让快慢指针同时指向 head 的后继结点
•
快指针往前走 k- 1 步,先走到第 k 个结点
•
快慢指针同时往后走一步，不断重复此步骤，直到快指针走到尾结点,此时的 slow 结点即为我们要找的倒序第 k 个结点
