主題
題目連結：
題目意譯：
反轉一個單向連結串列（Linked List）。
進階：
一個連結串列可被迭代地或是遞迴地反轉。你能兩個都實作出來嗎？
範例測資：
輸入： 1->2->3->4->5->NULL
輸出： 5->4->3->2->1->NULL
解題思維：
以範例說明迭代法（當然，如果給定的連結串列已經是 NULL 也不需要反轉了，直接回傳 NULL 即可）：
一開始令變數 last 指向 1 、 now 指向 1 的下一個，在這邊也就是 2 ，並另定一個變數為 buffer。
接著跑一迴圈，其進入條件為 now != NULL。當 now 非空時，將 buffer 設為 now->next （即 now 現在指向的節點，其下一個節點）。然後將 now->next 設為 last 。再來將 last 設為 now ，最後將 now 設為 buffer 。
因此原本的範例 1→2→3→4→5→NULL （藍色代表 now 、紫色為 last），
第一次迴圈執行結束會變為：
1←2 3→4→5→NULL
（會斷開是因為題目給定的 ListNode 型態只有一個指標 next 用來單向地指向下一個節點）
第二次後：
1←2←3 4→5→NULL
第三次：
1←2←3←4 5→NULL
第四次：
1←2→3←4←5
最後將原本連結串列的頭，也就是 1 的那個節點指向 NULL，整個連結串列即完成反轉。而新連結串列的頭，恰好為 last。因此回傳 last。
那麼遞迴法呢？同樣用範例測資舉例（假設函式名為 reverseList(ListNode *head)）：
遞迴終止條件：當目前的子連結串列之頭 head 沒有下一個節點時（head->next == NULL），直接回傳 head 即可。（因為單一節點不需要反轉）
而範例 1→2→3→4→5→NULL 的反轉過程如下：
遞迴第一層：令一指標 p 儲存子連結串列反轉之後的頭，也就是遞迴呼叫 reverseList(head->next)，也就是先將 head 之後的節點反轉。
遞迴第二層：所以現在變為 2→3→4→5→NULL 這個子問題（所以現在 head 為 2 。請注意，這個 head 跟上面的 head 是不同的變數，因為現在正在遞迴堆疊中的不同區域），
同樣也是令一 p （這邊也是與上面不同的 p） ＝ reverseList(head->next)
遞迴第三層：變為 3→4→5→NULL 這個子問題，令 p ＝ reverseList(head->next)
遞迴第四層：子問題 4→5→NULL ，令 p ＝ reverseList(head->next)
遞迴第五層：子問題 5→NULL，而 5 指向 NULL ，所以直接回傳即可。
回到第四層：將 head->next->next （也就是將 head 下一個節點的下一個節點）指向 head 所指向的節點，然後將 head->next 指向 NULL。因此現在整體結構看起來像是
1→2→3 NULL←4←5
（請注意，在第四層實際上看不到前面的 1→2→3 ，這邊只是示意整體的當前架構）
然後因為 p 指向的是 5 的那個節點，而且是反轉後的頭，因此回傳 p 。
回到第三層：一樣將 head->next->next （雖然 p 已經指向原本最後的節點 5 ，但是現在這層的 head->next 仍指向 4 ，沒有被動過）指向 head，然後將 head->next 變為 NULL。因此結構變為
1→2 NULL←3←4←5
然後回傳 p 。
回到第二層：head->next->next 以及 head->next 的變更後，結構變為
NULL←2←3←4←5
然後回傳 p 。
回到第一層：操作後，結構變為
NULL←1←2→3←4←5
回傳 p 。
而遞迴此時就成功地將整個串列反轉了。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
