第11章字符串反转

课程目录第11章字符串反转

第11章：字符串反转——手写 reverse 函数（原地反转与新建反转）

字符串反转，这题目看着简单吧？

我面试过不少人，上来就写 strrev 的，直接 pass。不是我不会用库函数，而是你连底层怎么倒腾字符都说不清楚，我怎么放心让你去碰内存管理？

今天咱们就把反转这件事聊透。两种方式：原地反转和新建反转。各有各的坑，各有各的妙用。

11.1 原地反转：不申请新内存，直接改原串

原地反转，说白了就是两个指针往中间怼。一个指向头，一个指向尾，交换字符，然后头指针往后走，尾指针往前走，直到碰头。

我当年第一次写这个函数，犯了个低级错误——忘了处理空串和单字符的情况。结果线上崩了，被运维大哥追着骂了半小时。嗯，从那以后我写任何字符串函数，第一件事就是判空。

来看代码：

#include <stdio.h>
#include <string.h>

void reverse_inplace(char *str) {
    if (str == NULL) return;          // 空指针，直接滚蛋

    int len = strlen(str);
    if (len <= 1) return;             // 没啥好反转的

    char *left = str;
    char *right = str + len - 1;
    char temp;

    while (left < right) {
        temp = *left;
        *left = *right;
        *right = temp;

        left++;
        right--;
    }
}

这里有个细节：while (left < right) 而不是 while (left != right)。为什么？因为偶数长度时，两个指针会交错而过，用 != 会死循环。你想想看，长度4的字符串，第一次交换后 left=1, right=2，第二次 left=2, right=1，永远不相等。我见过不止一个新手栽在这上面。

  核心要点：原地反转的时间复杂度 O(n)，空间复杂度 O(1)。不额外申请字符数组，只用了几个临时变量。

11.2 新建反转：原串不动，生成新串

有些场景下你不能改原串。比如原串是只读区、或者你后面还要用原顺序。这时候就得新建一个字符串来存反转结果。

新建反转的思路更直白：从原串末尾往前遍历，依次把字符拷贝到新串里。但这里有个大坑——别忘了结尾的 '\0'。

我曾经帮一个同事排查 bug，他写的反转函数返回的字符串打印出来后面跟着一堆乱码。我一看代码，好家伙，新串末尾没加 '\0'。C 语言的字符串全靠 '\0' 结尾，你漏了它，printf 就会一直读到碰见内存里的随机 0 为止。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* reverse_new(const char *str) {
    if (str == NULL) return NULL;

    int len = strlen(str);
    char *new_str = (char*)malloc(len + 1);  // +1 给 '\0'
    if (new_str == NULL) return NULL;        // 内存分配失败

    int i;
    for (i = 0; i < len; i++) {
        new_str[i] = str[len - 1 - i];
    }
    new_str[len] = '\0';                     // 手动加结束符

    return new_str;
}

注意看 malloc(len + 1)。多出来的一个字节就是给 '\0' 留的位置。很多初学者只分配 len 个字节，结果写 '\0' 的时候越界了。这种 bug 在调试时很难复现，因为越界不一定立刻崩溃，但会在某个夜深人静的晚上突然炸给你看。

警告：调用 reverse_new 后，调用方必须 free() 释放内存。否则就是内存泄漏。我建议你在函数注释里明确写上「返回值需要调用者 free」。

11.3 两种方式的对比

对比维度	原地反转	新建反转
是否修改原串	是	否
空间复杂度	O(1)	O(n)
适用场景	原串可写，且后续不再需要原顺序	原串只读，或需要保留原串
内存管理	无额外负担	调用者需 free
实现难度	中等（指针操作易出错）	简单（但易忘 '\0'）

我个人习惯是：能原地就原地。少一次 malloc 就少一次出错机会。但如果是写库函数给别人用，我倾向于提供新建版本，因为调用者不一定希望原串被改。

11.4 避坑指南：我踩过的那些雷

空指针与空串：任何字符串函数的第一行都应该是判空。别嫌啰嗦，线上事故往往就缺这一行。
中文字符问题：UTF-8 编码的中文占 3 个字节。如果你用上面的函数反转包含中文的字符串，会得到一堆乱码。因为一个中文字符被拆成了三个字节，反转后顺序全乱了。我曾在日志处理模块里踩过这个坑，后来改用宽字符 wchar_t 才解决。
const 修饰符：如果原串声明为 const char *，你不能把它传给原地反转函数。编译器会报 warning，但很多新手直接强转去掉 const，这是未定义行为。老老实实用新建反转。
性能考量：原地反转的缓存局部性更好。因为两个指针都在同一个数组里移动，CPU 缓存命中率高。新建反转需要同时访问两个数组，如果字符串很大（比如几 MB），性能差距会很明显。

11.5 知识体系：一张图看懂字符串反转

下面这张 SVG 图总结了本章的核心逻辑。我建议你把它存下来，面试前瞄一眼，思路就全回来了。

11.6 写在最后

字符串反转看起来简单，但它是很多复杂算法的基础。比如回文判断、大整数加法、括号匹配，底层都离不开反转的思想。

我建议你把上面两个函数背下来，手写几遍。面试时面试官让你写反转，你刷刷刷写完，再顺带讲一下两种方式的区别和适用场景，绝对加分。

记住：写 C 代码，永远把内存安全放在第一位。功能可以慢慢调，内存泄漏和越界一旦上线，那就是事故。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录