【算法思想·链表】单链表的花式反转方法汇总
【算法思想·链表】单链表的花式反转方法汇总
本文是一篇关于链表反转算法的详细教程。从基础的单链表反转开始，逐步深入到反转链表的前N个节点、反转链表的一部分，以及K个一组反转链表等更复杂的场景。文章通过对比迭代和递归两种实现方式，详细解释了每种算法的思路和代码实现，并配有可视化面板帮助理解。
1、概述
反转单链表的迭代解法不是一个困难的事情，但是递归实现就有点难度了。如果再加一点难度，让你仅仅反转单链表中的一部分，你是否能够同时用迭代和递归实现呢？再进一步，如果让你 k 个一组反转链表，阁下又应如何应对？
本文就来由浅入深，一次性解决这些链表操作的问题。我会同时使用递归和迭代的方式，并结合可视化面板帮助你理解，以此强化你的递归思维以及操作链表指针的能力。
2、反转整个单链表
在 力扣/LeetCode 中，单链表的通用结构是这样的：
# 单链表节点的结构
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
单链表反转是一个比较基础的算法题，力扣第 206 题「反转链表」就是这个问题。
迭代解法
这道题的常规做法就是迭代解法，通过操作几个指针，将链表中的每个节点的指针方向反转，没什么难点，主要是指针操作的细节问题。
class Solution:
# 反转以 head 为起点的但链表
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
# 由于单链表的结构，至少要用三个指针才能完成迭代反转
# cur 是当前遍历的节点，pre 是 cur 的前驱结点，nxt 是 cur 的后继结点
pre, cur, nxt = None, head, head.next
while cur is not None:
# 逐个结点反转
cur.next = pre
# 更新指针位置
pre = cur
cur = nxt
if nxt is not None:
nxt = nxt.next
# 返回反转后的头结点
return pre
操作指针的小技巧
上面操作单链表的代码逻辑不复杂，而且也不止我这一种正确的写法。但是操作指针的时候，有一些很基本、很简单的小技巧，可以让你写代码的思路更清晰：
1、一旦出现类似 **
nxt.next
这种操作，就要条件反射地想到，先判断
nxt
是否为 None**，否则容易出现空指针异常。
2、注意循环的终止条件。你要知道循环终止时，各个指针的位置，这样才能保返回正确的答案。如果你觉得有点复杂想不清楚，那就动手画一个最简单的场景跑一下算法，比如这道题就可以画一个只有两个节点的单链表
1->2
，然后就能确定循环终止后各个指针的位置了。
递归解法
上面的迭代解法操作指针虽然有些繁琐，但是思路还是比较清晰的。如果现在让你用递归来反转单链表，你有啥想法没？
对于初学者来说可能很难想到，这很正常。如果你学习了后文的二叉树系列算法思维，回头再来看这道题，才有可能自己想出这个算法。
因为二叉树结构本身就是单链表的延伸，相当于是二叉链表嘛，所以二叉树上的递归思维，套用到单链表上是一样的。
递归反转单链表的关键在于，这个问题本身是存在子问题结构的。
比方说，现在给你输入一个以
1
为头结点单链表
1->2->3->4
，那么如果我忽略这个头结点
1
，只拿出
2->3->4
这个子链表，它也是个单链表对吧？
那么你这个
reverseList
函数，只要输入一个单链表，就能给我反转对吧？那么你能不能用这个函数先来反转
2->3->4
这个子链表呢，然后再想办法把
1
接到反转后的
4->3->2
的最后面，是不是就完成了整个链表的反转？
reverseList(1->2->3->4) = reverseList(2->3->4) -> 1
这就是「分解问题」的思路，通过递归函数的定义，把原问题分解成若干规模更小、结构相同的子问题，最后通过子问题的答案组装原问题的解。
在后面的教程中会有专门的章节讲解和练习这种思维，这里不展开。
先来看看递归反转单链表的代码实现：
class Solution:
# 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
def reverseList(self, head):
if head is None or head.next is None:
return head
last = self.reverseList(head.next)
head.next.next = head
head.next = None
return last
这个算法常常拿来显示递归的巧妙和优美，我们下面来详细解释一下这段代码，最后在给出可视化面板，你可以自己动手探究一下递归过程。
对于「分解问题」思路的递归算法，最重要的就是明确递归函数的定义。具体来说，我们的
reverseList
函数定义是这样的：
输入一个节点
head
，将「以
head
为起点」的链表反转，并返回反转之后的头结点。
明白了函数的定义，再来看这个问题。比如说我们想反转这个链表：
那么输入
reverseList(head)
后，会在这里进行递归：
ListNode last = reverseList(head.next);
不要跳进递归（你的脑袋能压几个栈呀？），而是要根据刚才的函数定义，来弄清楚这段代码会产生什么结果：
这个
reverseList(head.next)
执行完成后，整个链表就成了这样：
并且根据函数定义，
reverseList
函数会返回反转之后的头结点，我们用变量
last
接收了。
现在再来看下面的代码：
head.next.next = head;
接下来：
head.next = null;
return last;
神不神奇，这样整个链表就反转过来了！递归代码就是这么简洁优雅，不过其中有两个地方需要注意：
1、递归函数要有 base case，也就是这句：
if (head == null || head.next == null) {
return head;
}
意思是如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。
2、当链表递归反转之后，新的头结点是
last
，而之前的
head
变成了最后一个节点，别忘了链表的末尾要指向 null：
head.next = null;
3、反转链表前 N 个节点
这次我们实现一个这样的函数：
# 将链表的前 n 个节点反转（n <= 链表长度）
def reverseN(head: ListNode, n: int):
比如说对于下图链表，执行
reverseN(head, 3)
：
迭代解法
迭代解法应该比较好写，在之前实现的
reverseList
基础上稍加修改就可以了：
def reverseN(head: ListNode, n: int):
if head is None or head.next is None:
return head
pre, cur, nxt = None, head, head.next
while n > 0:
cur.next = pre
pre = cur
cur = nxt
if nxt is not None:
nxt = nxt.next
n -= 1
# 此时的 cur 是第 n + 1 个节点，head 是反转后的尾结点
head.next = cur
# 此时的 pre 是反转后的头结点
return pre
4、反转链表的一部分
我们可以再进一步，给你一个索引区间，让你把单链表中这部分元素反转，其他部分不变。
力扣第 92 题「反转链表 II」就是这个问题：
给你单链表的头指针
head
和两个整数
left
和
right
，其中
left <= right
。请你反转从位置
left
到位置
right
的链表节点，返回 反转后的链表 。
示例 1：
**输入：**head = [1,2,3,4,5], left = 2, right = 4
**输出：**[1,4,3,2,5]
示例 2：
**输入：**head = [5], left = 1, right = 1
**输出：**[5]
提示：
- 链表中节点数目为
n - 1 <= n <= 500
- -500 <= Node.val <= 500
- 1 <= left <= right <= n
进阶： 你可以使用一趟扫描完成反转吗？
迭代解法
纯迭代的思路比较直接，可以先找到第
m - 1
个节点，然后复用之前实现的
reverseN
函数就行了：
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if m == 1:
return self.reverseN(head, n)
# 找到第 m 个节点的前驱
pre = head
for i in range(1, m - 1):
pre = pre.next
# 从第 m 个节点开始反转
pre.next = self.reverseN(pre.next, n - m + 1)
return head
def reverseN(self, head: ListNode, n: int) -> ListNode:
if head is None or head.next is None:
return head
pre, cur, nxt = None, head, head.next
while n > 0:
cur.next = pre
pre = cur
cur = nxt
if nxt is not None:
nxt = nxt.next
n -= 1
# 此时的 cur 是第 n + 1 个节点，head 是反转后的尾结点
head.next = cur
# 此时的 pre 是反转后的头结点
return pre
5、K 个一组反转链表
这个问题经常在面经中看到，而且力扣上难度是 Hard，看下题目：
给你链表的头节点
head
，每
k
个节点一组进行翻转，请你返回修改后的链表。
k
是一个正整数，它的值小于或等于链表的长度。如果节点总数不是
k
的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
示例 1：
**输入：**head = [1,2,3,4,5], k = 2
**输出：**[2,1,4,3,5]
示例 2：
**输入：**head = [1,2,3,4,5], k = 3
**输出：**[3,2,1,4,5]
提示：
- 链表中的节点数目为
n - 1 <= k <= n <= 5000
- 0 <= Node.val <= 1000
进阶：你可以设计一个只用
O(1)
额外内存空间的算法解决此问题吗？
有了前面的层层铺垫，它真的有那么难吗？其实只要你运用一下「分解问题」的思维，然后直接复用前面的
reverseN
函数就行了。
思路分析
认真思考一下可以发现这个问题具有递归性质。
比如说我们对这个链表调用
reverseKGroup(head, 2)
，即以 2 个节点为一组反转链表：
如果我设法把前 2 个节点反转，那么后面的那些节点怎么处理？后面的这些节点也是一条链表，而且规模（长度）比原来这条链表小，这就叫规模更小，结构相同的子问题。
我们可以把原先的
head
指针移动到后面这一段链表的开头，然后继续递归调用
reverseKGroup(head, 2)
：
发现了递归性质，就可以得到大致的算法流程：
1、先反转以
head
开头的
k
个元素。这里可以复用前面实现的
reverseN
函数。
2、将第
k + 1
个元素作为
head
递归调用
reverseKGroup
函数。
3、将上述两个过程的结果连接起来。
代码实现
结合上面的逐步讲解，代码就可以直接写出来了。我这里就用迭代形式的
reverseN
函数，你想用递归形式的也可以：
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head: return None
# 区间 [a, b) 包含 k 个待反转元素
a = b = head
for _ in range(k):
# 不足 k 个，不需要反转了
# 一定是先判断，后移动，否则可能踩在None上
if b is None: return head
b = b.next
# 反转前 k 个元素
newHead = self.reverseN(a, k)
# 此时 b 指向下一组待反转的头结点
# 递归反转后续链表并连接起来
a.next = self.reverseKGroup(b, k)
return newHead
# 上文实现的反转前 N 个节点的函数
def reverseN(self, head: ListNode, n: int) -> ListNode:
if not head or not head.next:
return head
pre, cur, nxt = None, head, head.next
while n > 0:
cur.next = pre
pre = cur
cur = nxt
if not nxt:
nxt = nxt.next
n -= 1
head.next = cur
return pre