如何用常数空间、低于O(n²)的时间交换char*字符串中的两个单词

核心解法：三次局部反转法 #

该方案仅使用常数级额外空间，时间复杂度为O(n)，完全满足题目要求。原理如下：
假设我们有两个连续单词A、B，总长度为firstWordLen + secondWordLen，我们的目标是将AB转换为BA，仅需要三步反转操作：

1. 反转整个字符串AB，得到B^T A^T（上标T表示字符串反转）
2. 反转前secondWordLen个字符（也就是反转后的B^T），得到B A^T
3. 反转后firstWordLen个字符（也就是A^T），最终得到BA

以题目示例验证：

• 原串AB = "hellosir"，A是hello（长度5），B是sir（长度3）
• 第一步反转整个串得到B^T A^T = "risolleh"
• 第二步反转前3个字符，B^T = "ris"反转后为B = "sir"，当前串为sirloleh
• 第三步反转后5个字符，A^T = "loleh"反转后为A = "hello"，最终得到sirhello

完整可运行代码 #

// 辅助函数：反转[start, end)左闭右开区间内的字符
void reversePart(char* start, char* end) {
    char temp;
    end--; // 移动到区间最后一个有效字符位置
    while (start < end) {
        // 原地交换两个字符，仅用1个临时变量
        temp = *start;
        *start = *end;
        *end = temp;
        start++;
        end--;
    }
}

char* swapWords(char* str, int firstWordLen, int secondWordLen) {
    // 边界异常直接返回原指针
    if (str == 0 || firstWordLen <= 0 || secondWordLen <= 0) {
        return str;
    }
    int totalLen = firstWordLen + secondWordLen;
    // 执行三次反转
    reversePart(str, str + totalLen);
    reversePart(str, str + secondWordLen);
    reversePart(str + secondWordLen, str + totalLen);
    return str;
}

注意事项 #

调用该函数时，传入的str必须是可修改的字符数组，不能直接传入字符串常量（C语言中字符串常量存储在只读内存区，修改会触发段错误）。正确调用示例：

int main() {
    char s[] = "hellosir";
    char* res = swapWords(s, 5, 3);
    printf("%s\n", res); // 输出sirhello
    return 0;
}

内容的提问来源于stack exchange，提问作者A S