來源于「Krahets」的《圖解算法數據結構》
https://leetcode.cn/leetbook/detail/illustration-of-algorithm/
鏈表反轉的遞歸要點
- 遞歸終止條件為當前節點為空,表明遍歷到了鏈表尾部
- 遞歸函數傳入參數為當前節點的下一個節點
- 按照是否重新開辟存儲空間分類
- 下面只寫了遞歸做法,遍歷做法略
單指針
- 如果重新開辟空間存儲反轉后的鏈表,則只需要一個指針:即遞歸到表尾然后函數返回后依次存入新的空間
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);}
};