指標反轉陣列題解

簡潔題意

實作 void array_reverse(int *head, int *tail);。head 指向陣列第一個元素、tail 指向最後一個元素，請把整個陣列原地反轉。

兩個指標往中間夾

反轉的意思是：第一個換到最後一個、第二個換到倒數第二個⋯⋯對稱的兩格互換。所以讓兩個指標各站一端，換完就一起往中間走一步：

交換 *head 與 *tail（跟交換指標指向的整數完全同一招，一樣要暫存變數）。
head++、tail--：兩個位置各往中間移一格。
兩個指標還沒碰頭就重複。

拿範例 1 的 1 2 3 4 5 走一次：

這一輪換的	換完的陣列
`1` 與 `5`	`5 2 3 4 1`
`2` 與 `4`	`5 4 3 2 1`
碰頭了，停	`5 4 3 2 1`

正中央的 3 沒有對象可換，本來就不用動。

迴圈條件：指標可以比大小

「還沒碰頭」怎麼寫？11.3 提過一件事：同一個陣列裡的指標可以互相比大小，位置在前面的比較小。所以直接寫

while (head < tail)

就是「head 還在 tail 左邊」。長度是奇數時，兩個指標會停在正中央那格（head == tail，不滿足 <）；長度是 \(1\) 時，一開始就不會進迴圈——兩個邊界都自動處理好了。

（寫成 head <= tail 也會過，差別只是中間那格會自己跟自己換一次，做了白工而已。）

若陣列長度是 \(n\)，大約換 \(n / 2\) 次，時間複雜度 \(O(n)\)。

參考程式碼

void array_reverse(int *head, int *tail) {
    while (head < tail) {   // 兩個位置還沒碰頭
        int temp = *head;   // 交換 head 與 tail 指到的兩個值
        *head = *tail;
        *tail = temp;
        head++;             // 往右一格
        tail--;             // 往左一格
    }
}

常犯錯誤

交換 head 與 tail 兩個指標變數：int *temp = head; head = tail; tail = temp; 換到的是函式手上的兩張紙條，陣列一格都沒動。範例 1 會原封不動印出 1 2 3 4 5。
只換一次就結束：忘了迴圈，只交換頭尾。範例 1 印出 5 2 3 4 1。
先移動再交換：把 head++、tail-- 寫在交換前面，兩個端點就被跳過了。範例 1 印出 1 4 3 2 5。
相鄰兩兩交換：(1,2) 換、(3,4) 換⋯⋯那是把每一對前後對調，不是整段反轉。範例 1 印出 2 1 4 3 5。

小結

這四題把 11.2、11.3 的每個動作各練了一次：

題目	練到的動作
交換指標指向的整數	`*p = ⋯`：照位置把值寫回去
指標之間	指標 \(-\) 指標：兩個位置差幾格
指標陣列加總	指標的陣列、`NULL` 哨兵
指標反轉陣列	指標移動與比大小

回頭看這一單元的起點 sort(a, a + n)：a 是開頭的位置、a + n 是往後跳 \(n\) 格的位置——11.4 的 sort 收下的，就是這兩個位置。之後自己寫題幾乎不會再宣告指標，但看到這種寫法、或讀到別人用 C 寫的程式，你都認得了。

指標反轉陣列 題解