AI summary
type
status
date
slug
summary
category
tags
icon
password
反转单链表的迭代解法不是一个困难的事情，但是递归实现就有点难度了。如果再加一点难度，让你仅仅反转单链表中的一部分，你是否能够同时用迭代和递归实现呢？再进一步，如果让你 k 个一组反转链表，阁下又应如何应对？
本文就来由浅入深，一次性解决这些链表操作的问题，并且同时使用递归和迭代的方式。

反转整个链表

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
迭代法：
pre 记录前驱节点，cur 记录当前节点。通过 cur.next = pre 进行反转，然后 pre 和 cur 分别向前推进，最后返回 pre。
递归法：
先反转第二个节点往后的，再接上第一个。
这就是「分解问题」的思路，通过递归函数的定义，把原问题分解成若干规模更小、结构相同的子问题，最后通过子问题的答案组装原问题的解。
对于「分解问题」思路的递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverseList 函数定义是这样的：
输入一个节点 head，将「以 head 为起点」的链表反转，并返回反转之后的头结点。
值得一提的是，递归操作虽然简洁易懂，但并不高效。
递归解法和迭代解法相比，时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。

反转前 N 个节点

迭代法：
迭代解法应该比较好写，在之前实现的 reverseList 基础上稍加修改就可以了，注意连接反转后的和剩下的。
递归法：
先反转从第二个节点往后的 n-1 个节点，然后接上第一个以及剩下的节点。注意要记录后驱节点，否则就和剩下的失联了。

反转链表的一部分

再进一步，给你一个索引区间，让你把单链表中这部分元素反转，其他部分不变。

92. 反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。 进阶： 你可以使用一趟扫描完成反转吗？
题目输入索引区间 [m, n]（索引从 1 开始），仅仅反转区间中的链表元素。
迭代法：
先找到第 m-1 个节点，然后复用前面的 reverseListN 函数就行了。
递归法：
从第二个节点往后视为新的链表，反转 [m-1,n-1] 即可。m=1 时调用 reverseListN 。
代码同理，略。

K 个一组反转链表

这个问题经常在面经中看到，而且力扣上难度是 Hard。

25. K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
依然可以递归解决：
  1. 先反转以 head 开头的 k 个元素。这里可以复用前面实现的 reverseListN 函数。
  1. 将第 k + 1 个元素作为 head 递归调用 reverseKGroup 函数。
  1. 将上述两个过程的结果连接起来。
不要跳进递归（你的脑袋能压几个栈呀？），而是利用明确的定义来实现算法逻辑。

回文链表

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
单链表无法倒着遍历，无法使用双指针技巧。
那么最简单的办法就是，把原始链表反转存入一条新的链表，然后比较这两条链表是否相同。
链表兼具递归结构，树结构不过是链表的衍生。那么，链表其实也可以有前序遍历和后序遍历，借助二叉树后序遍历的思路，不需要显式反转原始链表也可以倒序遍历链表：
这么做的核心逻辑是什么呢？实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的，只不过我们利用的是递归函数的堆栈而已。 当然，无论造一条反转链表还是利用后序遍历，算法的时间和空间复杂度都是 O(N)。能不能不用额外的空间，解决这个问题呢？
优化空间复杂度：
  1. 先通过快慢指针来找到链表的中点
  1. 如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步
  1. 从slow开始反转后面的链表，现在就可以开始比较回文串了