LeetCode 25. Reverse Nodes in k-Group 题解

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, val0, nextNone): # 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 个一组翻转链表问题还可以应用于许多其他需要链表操作的场景。掌握链表翻转和递归的技巧对于解决这类问题非常重要。