C 語言字符串左旋轉算法：原地三步反轉法實現

問題定義

將字符串左旋 k 位。例："ABCD" 左旋 1 → "BCDA"，左旋 2 → "CDAB"。

三步反轉法（O(1) 空間，O(n) 時間）

1. 反轉前 k 個字符；
2. 反轉剩餘 n-k 個字符；
3. 反轉整個字符串。

例 "ABCD" k=1：
① "A" → "A"
② "BCD" → "DCB"
③ "ADCB" → "BCDA" ✓

代碼實現

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

void reverse(char *s, int l, int r) {
    while (l < r) {
        char tmp = s[l];
        s[l++] = s[r];
        s[r--] = tmp;
    }
}

void leftRotate(char *str, int k) {
    int n = strlen(str);
    if (n == 0) return;
    k %= n;                 // 處理 k > n
    reverse(str, 0, k-1);
    reverse(str, k, n-1);
    reverse(str, 0, n-1);
}

int main() {
    char str[20] = "abcdefgh";
    int k;
    printf("原字符串: %s\n", str);
    printf("輸入左旋位數: ");
    scanf("%d", &k);
    leftRotate(str, k);
    printf("左旋後: %s\n", str);
    return 0;
}

原代碼問題分析

原代碼嘗試用尾部緩衝區拷貝實現，存在：

• 緩衝區溢出風險（未檢查剩餘空間）；
• 邏輯複雜且難維護；
• 未處理 k > n 情況。

三步反轉法是標準庫（如 std::rotate）通用實現，強烈推薦。