來源于「Krahets」的《圖解算法數據結構》
https://leetcode.cn/leetbook/detail/illustration-of-algorithm/

鏈表反轉的遞歸要點

1. 遞歸終止條件為當前節點為空，表明遍歷到了鏈表尾部
2. 遞歸函數傳入參數為當前節點的下一個節點
3. 按照是否重新開辟存儲空間分類
4. 下面只寫了遞歸做法，遍歷做法略

單指針

• 如果重新開辟空間存儲反轉后的鏈表，則只需要一個指針：即遞歸到表尾然后函數返回后依次存入新的空間

void reverse(vector<int>& reversedList, ListNode* node)
{if(!node) return;reverse(reversedList, node->next);reversedList.push_back(node->val);
}class Solution {
public:vector<int> reverseBookList(ListNode* head) {vector<int> reversedList;reverse(reversedList, head);return reversedList;}
};

雙指針

• 如果在原地反轉，則需要兩個指針，一個為指向當前節點 cur，另一個指向當前節點的前一個節點 pre
• 當 cur 為空節點時，此時 pre 為鏈表的最后一個節點，返回 pre 作為表頭
• 傳參時，cur 傳入 cur->next，pre 傳入 cur
• 每次都接收返回的結果，但這個結果一直是最后一個節點不變
• 遍歷逐層返回時進行指針的指向修改，也就是 cur->next = pre

class Solution {
public:ListNode* reverseList(ListNode* cur, ListNode* pre){//當前節點為最后一個節點的下一個節點時，將最后一個節點作為鏈表頭返回if(!cur) return pre;ListNode* res = reverseList(cur->next, cur);cur->next = pre;return res;}ListNode* trainningPlan(ListNode* head) {return reverseList(head, nullptr);}
};