206. 反轉鏈表

思路

在遍歷時，如果直接修改指針方向，會沒辦法繼續遍歷下去。
因此需要中間變數next用來存原先下一個節點。

程式碼

鏈表

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        while(head != nullptr) {
            ListNode* next = head->next; // 暫存下一個位置
            head->next = prev; // 反轉指針，指向前一個
            prev = head; // 更新兩個變數
            head = next;
        }
        return prev;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$