后台经常有人跑来问我双指针反转字符串这题到底该怎么写说实话第一次看到这道题我也觉得简单到有点“无聊”一个for循环倒着拷贝不就行了。但你真去面一次试或者认真刷一遍题就知道这题考的根本不是“会不会反转”而是你懂不懂原地操作、能不能把边界和类型处理干净。LeetCode 344 那道题几乎每个刷题的人都写过但我面试别人的时候超过一半的人讲不清楚“为什么双指针能原地反转”。这篇内容就是想把这件事彻底掰开揉碎讲清楚从最底层的思路到 C 的几种写法再到扩展应用和踩坑经验适合刚学算法的同学也适合准备面试的人做一次查漏补缺。1. 项目概述一个看似简单却值得拆解的题目1.1 题目到底在问什么常见的题目描述是编写一个函数输入一个字符数组s将字符串反转但不能额外分配另一个数组必须原地修改输入数组使用O(1)的额外空间完成。有的变体会给string有的要求返回新字符串但核心永远是“原地”两个字。很多第一次接触的人会愣住不新开数组怎么反转其实仔细想想就明白了。反转的本质是“把第一个字符和最后一个字符对调把第二个字符和倒数第二个对调一直对调到中间”。两个人面对面左边的人往右走右边的人往左走走到碰头就算结束。这就是双指针最纯粹的样子一个指针指向待处理区间的最左端另一个指针指向最右端在循环中逐步向中间收敛。这道题的价值不在“反转”这个动作本身而在于它逼着你建立一种空间敏感度。你写一个临时数组当然也能得到正确结果但复杂度面试官不会满意双指针解法只用两个下标或者迭代器不申请任何额外数组让空间复杂度从O(n)降到O(1)这才是题目真正想考察的东西。1.2 为什么双指针是“标准答案”如果先写一个最朴素的版本思路会非常直白新建一个等长的字符数组然后从原数组尾部开始遍历按顺序填进新数组vectorchar copy(s.rbegin(), s.rend()); // 反序拷贝这个写法不是不行但它开了新空间违背了“原地反转”的核心约束。双指针解决问题的优势就在这里每次只交换两个位置上的元素并且这两个位置的信息都已经被“指针”记了下来。不需要额外数组去保存“等一下要用哪个位置的元素”因为左右指针自己就知道该往哪移动。你可以把反转过程想成“翻煎饼”。一排煎饼从左到右依次放着你想让顺序颠倒不需要把它们全部端到另一个盘子里只需要从两头开始把最左和最右对调然后不断向中间推进。每对煎饼只需要一次交换交换完的位置就固定了后续操作不会再碰它们。这个思路放到字符数组上就是标准双指针。1.3 整体方案选型先副本、再双指针、最后标准库我的建议是练习时按三个阶段走。第一遍允许自己写副本法把结果做对第二遍强迫自己改成原地双指针体会空间复杂度从O(n)变成O(1)的过程第三遍再去看std::reverse的源码和实现思路理解标准库为什么长这样。第一次就背std::reverse的模板没有意义因为你不知道它内部是怎么收敛的。实际刷题时如果题目没有特殊限制直接用std::reverse当然是最稳妥、最不容易出错的但面试官一旦追问“你能手动实现一下吗”你肚子里得有东西。所以这篇博文的主角永远是那两根指针。2. 双指针原理拆解核心逻辑与复杂度分析2.1 一左一右交换然后向中间走拿最经典的例子hello来走一遍流程。字符串有 5 个字符初始时left 0指向hright 4指向o。第一轮交换s[0]和s[4]得到oellh。然后left加 1 变成 1right减 1 变成 3。第二轮交换s[1]和s[3]交换的是e和l得到olleh。然后left变成 2right变成 2。第三轮此时left不再小于right循环结束。如果是偶数长度的字符串比如abcd过程更对称a和d换b和c换等到left已经跑到right的右边循环结束。奇数长度时最中间那个字符不需要动因为它本身就是反转后的中心位置。我用一个表格把hello的过程记录下来方便你在脑子里建立一个画面轮次leftright当前字符串交换结果初始04hello无104h-ooellh213e-lolleh322循环结束olleh看到没整个过程一共只执行了n / 2次交换整除向下取整。5 个字符交换 2 次中间字符原地不动四个字符交换 2 次全部完成。2.2 为什么可以原地完成反转很多人第一次会觉得奇怪不借助额外空间那交换的时候不是需要一个临时变量吗这个临时变量算不算额外空间这里要澄清语言层面用于交换临时值的单个变量在算法分析中通常不被算作“额外数组空间”因为它的空间是O(1)常量级。双指针原地反转的核心是交换操作只涉及两个确定位置上的元素不需要缓存整串数据。从信息论角度看反转一个序列本质上是改变元素之间的排列关系而不是生成新数据。既然目标只是重排那就可以通过“对称交换”实现。左边第i个位置最终应该放原串第n-1-i个位置上的字符双指针恰好把这两个位置配对每对处理完就再也不会被重复访问所以信息不丢失也不需要留备份。这就是“原地”能成立的底层原因。2.3 时间复杂度与空间复杂度到底是多少循环的次数是n / 2每一次swap不管用标准库还是手写临时变量都是常数时间操作所以总时间复杂度是O(n)。这个复杂度跟副本法一样毕竟任何反转算法最少也得检查每个字符一次。真正的区别在空间副本法申请了一个n大小的新数组空间O(n)双指针法只用了两个下标和一个临时变量空间O(1)。我在面试别人时最常听到的回答是“时间复杂度是 O(n/2)”这也不能算错但算法分析里常数因子会被忽略写成O(n)更标准。如果面试官从O(n/2)追问下去你只要回答“常数项可以省略”就行。复杂度分析的目的不是抠算多少次交换而是看数据规模变大时时间增长的趋势是线性的、平方的还是对数的。3. C 代码实现与实操细节3.1 最标准的 while 双指针写法写 C 解法时最常见的输入是vectorchar s。最标准的代码长这样void reverseString(vectorchar s) { int n (int)s.size(); if (n 2) return; int left 0; int right n - 1; while (left right) { swap(s[left], s[right]); left; --right; } }这里有个很容易被忽略的点s.size()返回的是size_t也就是无符号整数。如果你直接写成int right s.size() - 1;当s是空字符串时0 - 1会变成一个非常大的无符号数之后循环行为会完全失控。所以稳妥的做法是先把size()转成int或者单独判空。循环条件用left right而不是left right。原因很简单当两个指针相遇指向同一个元素时这个元素已经在正确位置了没必要再和自己交换一次。虽然用在配合std::swap时不会报错但它多做了一次无意义操作并且破坏了“循环次数严格等于 n/2”的直觉。如果将来你手痒换成异或交换left right就是灾难后面我会专门说。3.2 基于迭代器的双指针写法C 里另一个常见写法是用迭代器。vectorchar的迭代器是随机访问迭代器支持加法和减法所以可以这么做void reverseString(vectorchar s) { auto left s.begin(); auto right s.end(); if (left right) return; --right; while (left right) { swap(*left, *right); left; --right; } }这个写法在语义上更贴近 STL 风格而且不容易出现“int 和 size_t 比较”的类型问题。需要注意s.end()指向的是最后一个元素的下一位不是最后一个元素本身所以必须先--right再进入循环。迭代器写法的局限也很明显它依赖随机访问迭代器。如果你把vectorchar换成listcharleft right这个比较就没法编译了因为链表迭代器只支持!判断。好在反转字符串场景基本不会用list所以这个写法平时用完全没问题。我个人的习惯是刷题时用下标版因为更好解释写工程代码时用迭代器版因为更通用思路也更清晰。3.3 用 std::swap 还是手写临时变量标准库的std::swap内部通常做了优化和类型萃取对基本类型来说非常高效而且异常安全。刷题和面试时直接用swap(s[left], s[right])是最优选择。但有些面试官会故意问“你能不用std::swap实现吗”这时候你要能写出char tmp s[left]; s[left] s[right]; s[right] tmp;这其实就是std::swap的朴素版本。手写时最大的坑是类型不匹配比如左边是char右边你写了个auto就可能导致拷贝错误不过char类型很简单一般不会有事。网上还有一种流传很广的“异或交换”写法s[left] ^ s[right]; s[right] ^ s[left]; s[left] ^ s[right];我强烈不建议在反转字符串里用。原因有两个第一当left和right指向同一个地址时异或会把元素清成 0而前面提到有人喜欢用left right一旦相等就中招第二异或交换可读性差别人看代码要反应很久才能明白这是在交换。算法题讲究清晰、准确不是炫技老老实实用临时变量是最好的人效比。3.4 反转之后怎么打印出来C 篇“字符串反转怎么打印出来 c”是不少人搜过的关键词。很多新手搞混了“反转存储”和“打印输出”。如果函数已经原地修改了s打印只需要for (char c : s) { cout c; } cout endl;如果s是string类型直接cout s endl;就行如果s是vectorchar直接输出cout s是不行的因为vector没有重载这个输出运算符必须遍历或者先构造一个stringstring result(s.begin(), s.end()); cout result endl;还有一种比较“STL 风格”的写法copy(s.begin(), s.end(), ostream_iteratorchar(cout));这种写法本质上是把每个字符依次交给ostream_iterator输出。日常项目里我不太建议为了打印一个字符串搞这么花哨但知道有这么个东西看别人代码时不至于懵。打印这件事的重点是确认结果符合预期后面我会单独说测试用例。4. 扩展应用双指针思想不只是反转4.1 反转字符串里的单词顺序双指针反转字符串的经典变体是“反转字符串中的单词顺序”比如the sky is blue要变成blue is sky the。很多第一次看到这题的人会想先把所有单词塞到一个栈里再弹出来拼成新串。这样做当然可以但空间复杂度是O(n)不是最优。更巧妙的做法就是先整体反转整个字符串再从前往后逐个反转每个单词。举个例子原串the sky is blue整体反转后变成eulb si yks eht然后你再把每个连续字母段反转一次eulb反转成bluesi反转成isyks反转成skyeht反转成the最终得到blue is sky the。思路的核心仍然是双指针不过第一次是全串范围第二次是以空格为边界的局部范围。这个过程里最难处理的其实是空格边界。连续多个空格怎么办字符串首尾有空格怎么办不同题目要求不同有的要求保留空格数量有的要求删除多余空格。我的建议是先把“去掉多余空格”和“整体反转”分开写不要混在一次循环里否则调试会很痛苦。写完基础版再去优化边界条件这样思路不会乱。4.2 判断回文双指针的另一面反转字符串还有一种特别常见的姊妹题判断一个字符串是不是回文。回文的定义就是正着读和反着读一样比如racecar。用双指针判断时一个指针从头走一个指针从尾走逐个比较字符是否相等一旦发现不一样就返回false。如果题目进一步要求“忽略大小写、忽略非字母数字字符”代码会稍微复杂一点但整体框架不变bool isPalindrome(string s) { int left 0, right (int)s.size() - 1; while (left right) { while (left right !isalnum(s[left])) left; while (left right !isalnum(s[right])) --right; if (tolower(s[left]) ! tolower(s[right])) return false; left; --right; } return true; }这个题和反转字符串的区别在于反转是“交换两端的值”回文判断是“比较两端的值”。但指针移动的模式一模一样都是向中间收敛。你如果能把反转字符串的双指针写熟回文判断基本就是顺手的事。4.3 快慢指针双指针的另一种形态除了相向而行的双指针还有“快慢指针”也就是一个指针走得快一个指针走得慢典型应用是“移动零”、“数组去重”、“找链表中间节点”。虽然方向和反转字符串不同但底层思想一致用两个指针维护不同的语义位置在一次遍历里完成操作。拿“移动零”举例要求把所有 0 移到数组末尾同时保持非零元素的相对顺序。这时可以用一个慢指针slow指向“下一个可以放非零元素的位置”一个快指针fast从头遍历。快指针负责找非零元素找到后放到slow位置slow前进。一趟下来非零元素全部靠前最后把剩余位置填 0。你回头看反转字符串的双指针会发现都是“两指针协作、避免 O(n) 额外空间”的模式。这就是算法学习里常说的“做一题会一类”。5. 常见踩坑与排查心得5.1 中文输入和编码的坑如果你拿这道题去处理中文字符串比如你好直接用vectorchar反转会得到一堆乱码。这不是你代码写错了而是 C 里char只占一个字节而中文在 UTF-8 编码下通常占 3 个字节。你的 UTF-8 编码大致是E4 BD A0好的编码大致是E5 A5 BD整个字符串在内存里是E4 BD A0 E5 A5 BD。双指针反转的是单个char字节结果字节顺序完全颠倒解码出来自然是乱码。这个问题没有“一行代码”的简单解法。真正的处理方式是使用宽字符类型std::wstring和wchar_t或者在拿到字符串后先按 Unicode 码点拆成字符数组再反转最后重新编码。但在 LeetCode 这类平台上输入几乎都是纯 ASCII 的英文串不需要考虑中文。如果你在自己的项目里做字符串反转一定要先问清楚数据是什么编码。我踩过这个坑之后养成了一个习惯只要有中文字符串处理先用一个最简单的测试用例跑一遍看输出是否正常再写后续逻辑。5.2 小心 size_t 和无符号数的下溢前面提到了s.size() - 1的经典问题。size_t是无符号类型你如果写出这样的代码int right s.size() - 1;当s为空时s.size()等于 00 - 1在无符号运算里会变成18446744073709551615这样的巨大整数然后转成int多半变成-1或者某个诡异的数。更安全的是int n (int)s.size(); if (n 0) return; int left 0, right n - 1;一开始就在代码入口写好边界返回能省掉很多调试时间。你可能会觉得“我测试的时候传的都是非空字符串没问题”但面试官最爱干的事就是拿空字符串测试你的候选代码。边界条件不是可有可无的装饰而是代码质量的一部分。5.3 while(left right) 到底行不行我一直强调用left right那写成会怎样如果配合std::swap在left right时只是让同一个元素和自己交换结果不变程序不会报错。所以很多人觉得无所谓。但我见过不止一个新手在某个瞬间“灵机一动”把交换逻辑改成了异或运算然后在left right时直接把元素改成 0查半天查不出来。还有一点left right会让循环多走一次虽然那一次不产生实质变化但在白板推演复杂度时容易说错。面试时候选人说“我循环执行了 n/2 次因为 left right”会比“反正转对了”显得更清晰。所以我还是建议统一写既省事又严谨。5.4 测试用例该怎么设计这道题虽然小但测试用例覆盖好了能体现你的严谨性。我整理了一张表你可以直接拿去当自测清单输入预期输出用途空串边界aa单字符abba偶数长度abccba奇数长度验证中间字符ab cddc ba带空格的正常字符AAbbbbAA大小写混合跑用例的时候不要只盯着结果对不对还要注意有没有额外报错比如空串下right初始值异常、循环越界等等。拿这几个用例去跑自己的代码基本能暴露 90% 的边界问题。6. 个人心得把这道题内化成自己的技能我自己刷这道题的时候第一反应也是“这么简单的题有什么好写的”后来在给别人讲的时候才发现越是简单的题越能看出一个程序员对基础概念的掌握程度。双指针反转字符串本质上串联起了四个基础能力数组索引、循环边界、原地交换、复杂度分析。每一项都不难但合在一起很多人就讲不清楚了。有一个小习惯对我帮助很大不要只盯着代码看而是拿一张纸画出每一步的数组状态。把left和right的位置标出来把交换后数组的内容写下来你就会发现“指针怎么移动”比“指针是什么”重要得多。遇到奇数长度时中间元素不动、遇到偶数长度时两个指针刚好交错这些细节只靠脑内模拟很容易忽略。另外面试时别急着写代码。先把思路用口语说一遍“我会用一左一右两个下标往中间走依次交换。”这句话一说完面试官通常就会点头。接着你再开始写代码并把空串、单字符这些边界条件随手处理掉原地的空间复杂度也顺带提一句整个题就回答得很完整了。如果时间允许你还可以顺势说一句“这个思路还可以用在回文判断和反转单词顺序上”展示你的迁移能力。这道题写在简历上可能什么都不是但它真的是一把很好的钥匙。用它打开双指针的大门后面再遇到滑动窗口、链表操作、原地哈希你都会有一种熟悉感不过是两根指针配合不同的移动规则罢了。希望这篇能帮你少走一点弯路也欢迎你有自己的想法时多动手验证纸上得来终觉浅。