陣列與鏈表逆置算法完解：從雙指針交換到鏈表指標反轉

複雜度

時間 O(N/2) = O(N)，空間 O(1)。

二、單向鏈表逆置

核心思想：三指針迭代反轉

• r：新鏈表頭（已反轉部分）
• y：當前待處理節點
• t：暫存 y->next 防止斷鏈

逐步演示

// 初始：r=NULL, y=head
while (y != NULL) {
    t = y->next;   // (1) 備份下一節點
    y->next = r;   // (2) 反轉指向
    r = y;         // (3) 推進新頭
    y = t;         // (4) 推進舊鏈表
}
return r;          // 返回新頭

完整可執行範例

struct Node { int data; Node* next; };
Node* reverse(Node* x) {
    if (!x) return NULL;
    Node *r = NULL, *y = x, *t;
    while (y) {
        t = y->next;
        y->next = r;
        r = y;
        y = t;
    }
    return r;
}

複雜度

時間 O(N)（單次遍歷），空間 O(1)（原地反轉）。

來源：「C++」博客，原文連結：https://ljqy27.blog.51cto.com/1054/40153。