C语言实现字符串左旋K个字符的三种高效算法

晚来风

发布时间：2026-10-13| 7人浏览过

原创

在C语言开发与算法面试中，字符串处理是基础且高频的考点。其中，“将字符串左旋K个字符”不仅考察对指针操作的熟练度，更测试对数据变换规律的洞察力。本文将从朴素的逐个移动法出发，逐步推导出最优的“三次逆序旋转法”，并深入解析原地修改字符串的代码实现细节。

一、问题定义与直观理解

所谓“左旋”，即把字符串左侧的前 K 个字符移动到字符串末尾。例如： - 原始字符串："ABCDEF"
- 左旋 2 个字符后："CDEFAB"

我们需要编写一个函数 left_move(char* arr, int k)，在满足以下约束条件下完成操作：

安全性：避免空指针访问或未定义行为。
效率：尽量不使用额外的临时数组，争取空间复杂度为 O(1)。
通用性：能处理任意长度及左旋次数的情况。

二、方法一：朴素移位法（暴力模拟）

最直观的思路是将“左旋 1 次”的操作重复执行 K 次。每次操作时，取出第一个字符暂存，将其余所有字符向前移动一位，最后将暂存的字符放到末尾。

第 1 步：单次左旋动作实现

当我们需要将字符串 "abcd" 左旋 1 次得到 "bcda" 时，内存数据的流向如下：

这一过程虽然逻辑简单，但时间复杂度为 O(K * N)。当 K 很大时，效率较低，通常作为基准测试或初学者理解的起点。

第 2 步：封装循环调用

在实际编码中，我们通过外层循环控制左旋次数。代码结构如下：

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

void left_move(char* arr, int k) {
    assert(arr); // 确保指针有效
    int len = strlen(arr);
    
    for (int i = 0; i < k; i++) {
        char tmp = *arr; // 保存首字符
        for (int j = 0; j < len - 1; j++) {
            arr[j] = arr[j + 1]; // 前移覆盖
        }
        arr[len - 1] = tmp; // 末尾补入
    }
}

int main() {
    char arr[] = "abcdef";
    int x = 2;
    left_move(arr, x);
    printf("Result: %s\n", arr);
    return 0;
}

三、方法二：三次逆序旋转法（最优解）

为了实现更优的 O(N) 时间复杂度和 O(1) 空间复杂度，我们可以利用数学规律。观察发现，左旋字符串可以通过分段逆序再整体逆序来实现。这类似于魔方的还原步骤，逻辑严密且无需额外内存。

第 1 步：划分区域

假设我们要将 "ABCDEF" 左旋 2 个字符（即 K=2）。我们将字符串划分为两部分：

第一部分：前 K 个字符 [A, B]
第二部分：剩余字符 [C, D, E, F]

第 2 步：分别逆序两段

首先对第一部分和第二部分各自进行逆序操作：

[A, B] 变为 [B, A]
[C, D, E, F] 变为 [F, E, D, C]

此时字符串状态为："BAFEDC"。注意，此时每部分的内部顺序反转了，但两部分的相对位置未变。

第 3 步：整体逆序

对整个字符串进行最后一次逆序：

"BAFEDC" 逆序后变为 "CDEFAB"。这正是我们想要的结果！该方法的数学原理在于：对于序列 X Y，若先分别逆序得到 X^R Y^R，再整体逆序，则结果为 ((X^R Y^R)^R) = Y X，即实现了左右交换。

第 4 步：核心辅助函数 `reverse` 的实现

为了复用代码，我们先封装一个通用的逆序函数，使用双指针从两端向中间交换：

// 逆序区间 [left, right]

void reverse(char* left, char* right) {
    assert(left && right);
    while (left < right) {
        char tmp = *left;
        *left = *right;
        *right = tmp;
        left++;
        right--;
    }
}

第 5 步：组合调用逻辑

主逻辑只需三步调用于此即可：

void left_move_optimized(char* arr, int k) {
    assert(arr);
    int len = strlen(arr);
    if (k > 0 && k < len) { // 防止越界无效操作
        // 1. 逆序前k个
        reverse(arr, arr + k - 1);
        // 2. 逆序剩余部分
        reverse(arr + k, arr + len - 1);
        // 3. 整体逆序
        reverse(arr, arr + len - 1);
    }
}