C語言字串左旋轉演算法：三步反轉法完整實作

問題定義

給定字串 "ABCDE"，左旋 1 位得 "BCDEA"，左旋 2 位得 "CDEAB"。實現通用的字串左旋函數。

核心演算法：三步反轉法

時間複雜度 O(N)、空間複雜度 O(1)，原地操作：

1. 反轉前 k 個字元
2. 反轉剩餘字元
3. 整體反轉

範例：ABCDE，k=2
① 反轉前 2 字元 → BACDE
② 反轉後 3 字元 → BAEDC
③ 整體反轉 → CDEAB ✓

完整程式碼

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

// 反轉區間 [left, right] (指標版)
void reverse(char *left, char *right) {
    while (left < right) {
        char tmp = *left;
        *left++ = *right;
        *right-- = tmp;
    }
}

// 左旋 k 位
void left_rotate(char *str, int k, int len) {
    if (k <= 0 || k >= len) return;
    reverse(str, str + k - 1);       // 步驟 1
    reverse(str + k, str + len - 1); // 步驟 2
    reverse(str, str + len - 1);     // 步驟 3
}

int main() {
    char str[] = "ABCDE";
    int k, len = strlen(str);

    printf("請輸入旋轉位數 (1~%d)：", len - 1);
    scanf("%d", &k);
    while (k > len) {
        printf("數值過大，請重新輸入：");
        scanf("%d", &k);
    }

    left_rotate(str, k, len);
    printf("旋轉後：%s\n", str);
    return 0;
}

執行示例

請輸入旋轉位數 (1~4)：2
旋轉後：CDEAB

關鍵點解析

• 使用指標運算避免陣列下標開銷，效率更高。
• reverse 接受指標範圍，通用性強，可復用於其他反轉需求。
• 輸入驗證：防止 k 超過字串長度導致越界。

延伸應用

• 右旋：左旋 len - k 位即可。
• 循環位移陣列、字串查找 (KMP 前綴表構建) 等場景同理。