LeetCode 25. Reverse Nodes in k-Group 题解
题目描述
给你链表的头节点 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]
解题思路
方法：递归 + 链表翻转
思路：
- 首先检查链表的长度是否大于等于 k，如果不是，直接返回头节点
- 然后翻转前 k 个节点
- 递归地翻转剩余的链表
- 将翻转后的前 k 个节点与剩余翻转后的链表连接起来
复杂度分析：
- 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
- 空间复杂度：O(n/k)，递归调用的栈空间取决于递归的深度，最多为 O(n/k)。
代码实现
方法：递归 + 链表翻转
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 检查链表的长度是否大于等于 k
current = head
for _ in range(k):
if not current:
return head
current = current.next
# 翻转前 k 个节点
prev = None
current = head
for _ in range(k):
next_node = current.next
current.next = prev
prev = current
current = next_node
# 递归地翻转剩余的链表
head.next = self.reverseKGroup(current, k)
return prev
测试用例
测试用例 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]
测试用例 3：
输入：head = [1,2,3,4,5], k = 1输出：[1,2,3,4,5]
测试用例 4：
输入：head = [1], k = 1输出：[1]
总结
本题是链表的经典问题，主要考察对链表操作和递归的理解和应用。通过使用递归和链表翻转，我们可以高效地按 k 个一组翻转链表。
递归的核心思想是：将问题分解为翻转前 k 个节点和递归翻转剩余链表两部分，然后将两部分连接起来。链表翻转的核心思想是：使用三个指针（prev, current, next_node）来逐个翻转节点。
这种方法不仅适用于 K 个一组翻转链表问题，还可以应用于许多其他需要链表操作的场景。掌握链表翻转和递归的技巧，对于解决这类问题非常重要。
