一、题目描述编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。题目要求不要给另外的数组分配额外的空间必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题元素的类型为str函数无返回值None。示例输入s [h,e,l,l,o]输出无返回值s被修改为[o,l,l,e,h]输入s [H,a,n,n,a,h]输出无返回值s被修改为[h,a,n,n,a,H]二、解法一Python内置reverse()方法1. 思路分析Python列表内置了reverse()方法可直接原地反转列表完全符合题目“原地修改、O(1)空间”的要求是日常开发/刷题中最简洁的解法。2. 完整代码class Solution: def reverseString(self, s: List[str]) - None: Do not return anything, modify s in-place instead. # 直接调用列表内置的reverse方法原地反转列表 s.reverse()3. 代码解析s.reverse()列表的内置方法直接修改原列表无返回值底层实现为双指针交换时间和空间复杂度均为最优执行示例输入[h,e,l,l,o]→ 执行后s直接变为[o,l,l,e,h]。4. 复杂度分析时间复杂度O(n)需遍历列表一次完成所有元素的反转空间复杂度O(1)原地修改列表无额外空间占用。5. 优缺点优点代码极简一行解决问题符合Pythonic风格。缺点依赖语言内置方法无法体现算法核心思想三、解法二切片操作简洁但需注意“原地”1. 思路分析Python的切片语法s[::-1]可生成反转后的新列表但直接赋值s s[::-1]会创建新列表仅修改变量引用原数组未变不符合“原地修改”要求需用s[:] s[::-1]实现原地替换原列表的所有元素。2. 完整代码class Solution: def reverseString(self, s: List[str]) - None: Do not return anything, modify s in-place instead. # 关键s[:] 表示替换原列表的所有元素实现原地修改 s[:] s[::-1]3. 核心解析切片写法对比写法执行效果是否符合“原地修改”要求s s[::-1]创建反转后的新列表仅修改变量s的引用原数组内存地址未变内容未修改s[:] s[::-1]把反转后的元素逐个替换到原列表的内存空间中直接修改原数组内容4. 复杂度分析时间复杂度O(n)切片需遍历列表生成反转后的新列表再将新列表元素替换到原列表空间复杂度O(n)切片会生成一个临时的反转列表占用O(n)额外空间不符合题目“O(1)空间”的核心要求仅作为拓展解法。5. 优缺点优点代码简洁仅一行比双指针写法更短缺点空间复杂度不满足题目要求依赖Python切片特性跨语言无法复用四、解法三双指针法基础最优解1. 思路分析双指针是反转类问题的通用经典解法无语言依赖核心逻辑初始化左指针l指向列表头部索引0、右指针r指向列表尾部索引len(s)-1交换s[l]和s[r]的值左指针右移l 1右指针左移r - 1重复步骤2-3直到l r指针相遇/交叉无需继续交换。2. 完整代码class Solution: def reverseString(self, s: List[str]) - None: Do not return anything, modify s in-place instead. # 初始化左右指针 left, right 0, len(s) - 1 # 指针未交叉时循环l r 而非 l r避免中间元素重复交换 while left right: # 交换左右指针指向的元素Python无需临时变量直接解包交换 s[left], s[right] s[right], s[left] # 移动指针 left 1 right - 13. 执行过程以示例s [h,e,l,l,o]为例循环次数leftright交换前s交换后s指针移动104[“h”,“e”,“l”,“l”,“o”][“o”,“e”,“l”,“l”,“h”]left1, right3213[“o”,“e”,“l”,“l”,“h”][“o”,“l”,“l”,“e”,“h”]left2, right2结束22--循环终止4. 复杂度分析时间复杂度O(n)最多循环次n为列表长度每个循环仅做常数次操作空间复杂度O(1)仅使用两个指针变量完全符合题目“原地修改、O(1)空间”的核心要求。5. 优缺点优点1. 无语言依赖通用最优解2. 空间复杂度严格O(1)缺点 :代码量略多于内置方法/切片。五、解法四递归法理解递归思想1. 思路分析递归的核心是“分治终止条件”将“反转整个列表”的问题分解为“交换首尾元素 反转中间子列表”直到子列表长度≤1递归终止。2. 完整代码class Solution: def reverseString(self, s: List[str]) - None: Do not return anything, modify s in-place instead. # 调用递归函数初始左右指针为列表首尾 self.recursion(s, 0, len(s) - 1) # 递归函数反转s[left...right]区间内的元素 def recursion(self, s: List[str], left: int, right: int) - None: # 递归终止条件左指针 右指针子列表无元素/仅一个元素 if left right: return # 先递归反转中间子列表left1 到 right-1 self.recursion(s, left 1, right - 1) # 再交换当前首尾元素 s[left], s[right] s[right], s[left]3. 递归执行过程以s [h,e,l,l,o]为例reverseString(s) → 调用 recursion(s, 0, 4)recursion(s, 0, 4) → 调用 recursion(s, 1, 3)recursion(s, 1, 3) → 调用 recursion(s, 2, 2)recursion(s, 2, 2) → left right直接返回交换 s[1] 和 s[3] → s [h,l,l,e,o]交换 s[0] 和 s[4] → s [o,l,l,e,h]4. 复杂度分析时间复杂度O(n)每个元素仅被交换一次递归调用次数为空间复杂度O(n)递归调用会占用系统栈空间栈的深度为不符合题目“O(1)空间”要求仅用于算法思想学习。5. 优缺点优点锻炼递归思维理解“分治”思想缺点1.空间复杂度高2. 递归深度过大时可能触发栈溢出3. 实际开发中效率低于双指针六、总结1. 核心要点题目核心要求原地修改 O(1)空间双指针法和内置reverse()方法是最优解切片写法需注意s[:] s[::-1]才是原地修改s s[::-1]不符合要求双指针循环条件用left right而非left right避免中间元素重复交换。2. 解法选择建议场景推荐解法原因日常刷题/快速解题内置reverse()方法代码极简一行解决面试/算法学习双指针法通用、无语言依赖体现算法思想拓展思路/学习递归递归法理解分治和递归终止条件仅作语法拓展切片法需注意空间复杂度问题