C語言字符串左旋轉：三步反轉法標準實現

C語言字符串左旋轉：三步反轉法標準實現

實現字符串左旋 k 位。如 "AABCD" 左旋 1 → "ABCDA"，左旋 2 → "BCDAA"。採用原地三步反轉法，O(n) 時間 O(1) 空間。

算法步驟

1. 反轉前 k 個字符
2. 反轉第 k+1 到末尾字符
3. 反轉整個字符串

完整代碼

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>

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

int main() {
    char arr[10] = "AABCD";
    int len = strlen(arr) - 1;  // 最後有效字符索引
    int k;
    printf("輸入左旋位數：");
    scanf("%d", &k);
    
    char *start = &arr[0];
    char *end = arr + len;
    
    reverse(start, start + k - 1);      // 步驟 1
    reverse(start + k, end);            // 步驟 2
    reverse(start, end);                // 步驟 3
    
    printf("結果：%s\n", arr);
    system("pause");
    return 0;
}

演示過程 (k=2)

原串：A A B C D
步驟1 反轉前2：A A → A A (無變化)
步驟2 反轉後3：B C D → D C B
中間：A A D C B
步驟3 整體反轉：B C D A A
結果：B C D A A  ✓

邊界處理

• k >= 長度：取模 k %= len 或報錯
• k = 0：直接返回
• 空字符串：檢查指針有效性

對比：輔助數組法

void left_rotate_aux(char *src, char *dst, int k) {
    int len = strlen(src);
    k %= len;
    strcpy(dst, src + k);
    strncat(dst, src, k);
}

簡單但需 O(n) 額外空間。