常见编程模式之就地反转链表
6. 就地反转链表（In-place Reversal of a LinkedList）
基本原理及应用场景
在很多问题中，我们需要对一个链表中的节点连接进行反转，且通常需要原地进行，即不能使用额外的存储空间。这时我们可以使用就地反转链表模式，该模式本质上是一种迭代解法，流程如下图所示。首先设置一个变量 current 指向链表头部，以及另一个变量 previous 指向当前处理节点的前一个节点。下一步我们需要将当前节点 current 进行反转，将其指向前一个节点 previous，然后将 previous 指向当前节点，再将 current 移动到下一个节点，开始迭代直至遍历完成。
经典例题
206. 反转链表（Easy）
反转一个单链表。
「示例」：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
这道题可以采用就地反转链表模式，即迭代方法，参考上面的讲解，代码实现如下：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
curr, pre = head, None
while curr:
temp_next = curr.next
curr.next = pre
pre = curr
curr = temp_next
return pre
当然这道题也可以采用递归实现，但是使用了隐式的栈空间，且不是非常好理解：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
p = self.reverseList(head.next) # 一直递归到最后一个元素之前，返回p为head.next（即最后一个节点）
head.next.next = head # 在当前递归中将head.next的下一个节点反转为head
head.next = None # 清除当前节点的下一个节点，防止循环（实际上只对最后一个节点有用，前面的会自动修改）
return p
递归的原理可以通过下图理解（来自 Leetcode-王尼玛）：
92. 反转链表 II（Medium）
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
1 ≤ m ≤ n ≤ 链表长度。
「示例：」
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
这道题可以采用就地反转链表模式，由于只翻转部分位置，所以需要设置两个额外的节点进行标记，翻转完成后将翻转部分和未翻转的部分进行拼接。具体的代码实现如下：
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
if not head: return None
cur, prev = head, None
while m > 1: # 将cur移到开始反转的位置，prev移到其前一个节点
prev = cur
cur = cur.next
m, n = m - 1, n - 1 # 注意对n也进行处理，相当于n=n-m+1
tail, con = cur, prev # 设置两个额外节点，用于之后拼接链表
while n: # 执行就地反转链表模式
temp_next = cur.next
cur.next = prev
prev = cur
cur = temp_next
n -= 1
# 拼接头部
if con:
con.next = prev
else:
head = prev
# 拼接尾部（实际上最开始的prev被丢弃了）
tail.next = cur
return head
本题也可以采用递归方法进行求解，我们先定义一个反转前 n 个节点的子函数，然后递归至起始位置开始反转即可：
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
def reverseN(head, n):
if n == 1:
return head
p = reverseN(head.next, n - 1)
successor = head.next.next # 始终指向反转节点的后一个节点
head.next.next = head # 反转链表
head.next = successor # 将最后一个节点指向后面未反转的部分
return p
if m == 1: return reverseN(head, n)
head.next = self.reverseBetween(head.next, m - 1, n - 1)
return head
25. K 个一组反转链表（Hard）
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。k 是一个正整数，它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
「示例」：
给你这个链表：1->2->3->4->5：
- 当 k = 2 时，应当返回:
2->1->4->3->5 - 当 k = 3 时，应当返回:
3->2->1->4->5
这道题同样可以使用就地反转链表模式，我们需要构建一个反转子链表的函数，然后遍历目标链表，达到 k 个则进行反转，并将其拼接回主链表中。这里的关键技巧是通过哑结点来保证每次相同的遍历次数，以及方便最后的返回。具体的代码实现如下：
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
def reverse(head, tail):
# 翻转一个子链表，并且返回新的头与尾
prev = tail.next # 指向尾节点的下一个节点
curr = head
while prev != tail: # 不能用tail.next判断，其指向已经改变
temp_next = curr.next
curr.next = prev
prev = curr
curr = temp_next
return tail, head
dummy = ListNode(0) # 设置一个哑结点，方便进行k次遍历（作为pre）以及最终的返回
dummy.next = head
pre = dummy # pre为子链表的前一个节点，用于将子链表接回原链表
while head:
tail = pre
# 查看剩余的长度是否大于等于k
for i in range(k): # 从起始节点的前一个结点开始，刚好k次到尾部
tail = tail.next
if not tail:
return dummy.next # 不满足直接返回
temp_next = tail.next # 记录子链表的下一个节点
head, tail = reverse(head, tail) # 反转子链表
# 把子链表接回原链表，并设置新的pre与head
pre.next = head
tail.next = temp_next
pre = tail
head = tail.next
return dummy.next
腾讯云开发者
