題目

鏈接：206. 反轉鏈表 - 力扣（LeetCode）
給你單鏈表的頭節點 head ，請你反轉鏈表，并返回反轉后的鏈表。

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

class Solution {
public:ListNode* reverseList(ListNode* head) {}
};

思路 & 代碼

雙指針法

1. 雙指針：①cur指針指向頭節點；②pre指針初始化為 NULL。
2. 反轉：
   • 先保存 cur->next：temp = cur->next；
   • 反轉：pre = cur->next;
   • 移動：先移動pre， pre = cur；再移動cur， cur = temp;
3. 結束條件：cur == NULL
4. 返回鏈表：return pre；
   
   
   

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* pre = nullptr;while(cur){ListNode* temp = cur->next;cur->next = pre;pre = cur;cur = temp;}return pre;}
};

遞歸法

遞歸三部曲：

1. 確定遞歸函數的參數和返回值
   • 參數：需要在遞歸中進行處理的
   • 返回值：根據返回值來確定返回類型
2. 確定終止條件
3. 確定單層遞歸邏輯
   • 確定每一層遞歸需要處理的信息。就是重復調用自己的過程。

class Solution {
public:ListNode* reversed(ListNode* cur, ListNode* pre){if(cur == nullptr) return pre;ListNode* temp = cur->next;cur->next = pre;return reversed(temp,cur);}ListNode* reverseList(ListNode* head) {return reversed(head, nullptr);}
};