如何用双指针原地反转数组或字符串？

简化版

用对撞指针:left 从头、right 从尾,交换两者指向的元素,然后 left++、right--,向中间靠拢,直到相遇。这样原地把数组/字符串首尾对称交换,时间 O(n)、空间 O(1)。因为只需交换 n/2 次,是最简洁高效的反转方法。

详细版

void reverse(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char t = s[left]; s[left] = s[right]; s[right] = t; // 交换首尾
        left++; right--;                                    // 向中间靠拢
    }
}

left < right:相遇即停(中间元素不用动)。
每次交换一对对称位置的元素,总共交换 n/2 次。
原地:直接在原数组上交换,不开新数组,空间 O(1)。

完整版教学

一、核心思想:首尾对称交换

反转的本质是「第 i 个和第 n-1-i 个互换位置」。对撞指针恰好表达了这一点:left 和 right 从两端出发,每次交换它们指向的元素,再一起向中间移动。当两指针相遇(或交错),所有对称位置都交换完毕,数组就反转了。这比「开一个新数组、倒着拷贝」更省空间(O(1) vs O(n)),是反转的标准写法。

二、为什么只需交换 n/2 次

数组有 n 个元素,反转就是把 n/2 对「对称位置」互换。left 从 0 走到中间、right 从 n-1 走到中间,两者各走约 n/2 步就相遇。中间那个元素(奇数长度时)不需要动(它反转后还在原位)。所以总共交换 n/2 次,时间 O(n)、且常数很小。

三、走一个例子

s = ['h','e','l','l','o']
left=0,right=4: 交换 h,o → ['o','e','l','l','h']
left=1,right=3: 交换 e,l → ['o','l','l','e','h']
left=2,right=2: 相遇,停止
结果: "olleh"

四、Java 里为什么常用 char[] 而不是 String

Java 的 String 是不可变的——不能原地修改字符。所以要原地反转字符串,通常先转成 char[](可变数组),反转后再 new String(chars)。这是 Java 特有的细节。其它语言(如 C++ 的 string、Python 处理 list)可变的话可直接原地反转。面试写「反转字符串」题(LeetCode 344)要求原地、O(1) 空间,就是考对撞指针 + 这个语言细节。

五、常见变体

对撞指针反转是基础,衍生出很多题:

反转字符串中的单词:先整体反转,再逐个单词反转(或反过来)。
反转元音字母:两个指针相向,只在都指向元音时才交换。
验证回文串:对撞指针从两端向中间比较,不相等就不是回文(反转的「只读版」)。
反转链表:链表不能随机访问,不用对撞指针,而是三指针逐个改 next(见链表专题)——注意区分。

六、复杂度与要点

时间 O(n)、空间 O(1)(原地)。
要点:left < right 相遇即停;交换用临时变量;Java 字符串要先转 char[]。
和反转链表区分:数组/字符串能随机访问,用对撞指针交换;链表不能,用指针改向。

七、把不变量、推演与工程边界落到代码上

算法正确性的核心不是记住某个 while，而是始终维护这个不变量：每轮交换 left 与 right 后，两端各有一个元素进入最终镜像位置。

对应的状态推进是：left++、right—，直到 left>=right。每次推进前都应能解释“为什么被排除的部分不可能再包含答案”，否则只是碰巧通过样例。

初始化边界与状态
while 尚未结束:
    根据当前状态作出唯一可证明安全的选择
    更新边界、计数或局部结构
    断言不变量仍然成立
返回不变量在终止状态下推出的答案

复杂度不能只背一个符号。交换次数 floor(n/2)，总时间 O(n)。

带数字走一遍：[a,b,c,d,e] 交换 a/e、b/d 后得到 [e,d,c,b,a]。手算时要同时记录下标、区间含义和本轮排除的候选，才能暴露等号与边界错误。

核对项	结论
前提	要求底层可变；Java String 不可变，通常转 char[]
时间复杂度	O(n)
额外空间	O(1)，若 String 转数组则 O(n)
关键边界	循环条件用 left<right；注意 Unicode 代理对不能总按 char 安全反转
替代方案	反转单词或区间时先明确操作单位和边界

易错点：模板只有在前提和不变量一致时才成立；换了区间定义、重复值规则或输出语义，等号与推进方式就必须重新推导。

实现完成后至少检查五类用例：

空输入或题目允许的最小规模，验证初始化不会越界。
单元素与两个元素，验证循环条件和最后一次推进。
大量重复值，验证相等分支、稳定性或去重语义。
已满足目标性质与极端逆序/偏斜分布，观察最好和退化路径。
上面的数字样例逐轮手算，并与程序记录的状态轨迹逐项对照。

八、常见误区与追问

误区：只要记住模板就适用于所有输入。 本题成立的前提是“要求底层可变；Java String 不可变，通常转 char[]”，前提被破坏后必须换算法或重新证明。
误区：复杂度只写 O(n) 就算完整。 还要说明输入参数、预处理、递归栈以及最坏退化条件；本题的推导是“交换次数 floor(n/2)，总时间 O(n)”。
误区：重复值和边界值不会改变代码。 循环条件用 left<right；注意 Unicode 代理对不能总按 char 安全反转。
追问：为什么每次推进不会漏掉答案？ 因为始终维护“每轮交换 left 与 right 后，两端各有一个元素进入最终镜像位置”，被舍弃区域已由顺序或状态关系证明不可能更优。
追问：用一个数字例子怎么讲？ 可以从“[a,b,c,d,e] 交换 a/e、b/d 后得到 [e,d,c,b,a]”开始，逐轮写出状态与被排除区间。
追问：什么时候不该使用这个方案？ 当前提不满足或退化代价不可接受时，应考虑“反转单词或区间时先明确操作单位和边界”。
追问：如何设计自测避免只过样例？ 同时覆盖最小规模、重复值、极端分布、无解/边界解，并对关键状态加断言。

九、加强记忆

反转数组/字符串用对撞指针:left 头、right 尾,交换两者、再各自向中间移动,相遇即停,共交换 n/2 次,O(n) 时间、O(1) 空间(原地)。Java 字符串不可变,要先转 char[] 再反转。变体:反转单词、反转元音、回文判断(只读版对撞)。注意链表反转不用对撞指针(链表不能随机访问,用三指针改 next)。

简化版

详细版