力扣（LeetCode）官網 - 全球極客摯愛的技術成長平臺
經典問題反轉鏈表
這里給出四種解法
1.雙指針
這種方法是用一個next指針記錄當前節點的下一個節點，一個pre指針記錄當前節點的前一個節點。
只需要遍歷一遍鏈表就可以完成鏈表的反轉
class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode*pre,*curr;curr=head;pre=nullptr;while(curr){ListNode*next=curr->next;curr->next=pre;pre=curr;curr=next;}return pre;}
};2.棧
這種方法使用了額外的堆棧空間，但能夠有效地反轉鏈表。
class Solution {
public:ListNode* reverseList(ListNode* head) {// 如果鏈表為空或只有一個節點，直接返回原鏈表if (!head || !head->next)return head;stack<ListNode*> stk; // 創建一個堆棧，用于存儲鏈表節點ListNode* curr = head; // 創建指針curr，用于遍歷原始鏈表// 將鏈表節點逐個壓入堆棧while (curr) {stk.push(curr);curr = curr->next;}ListNode* newhead = stk.top(); // 堆棧的頂部節點作為新鏈表的頭部curr = newhead;// 從堆棧中彈出節點，并重新連接鏈表節點while (!stk.empty()) {curr->next = stk.top();curr = curr->next;stk.pop();}curr->next = nullptr; // 將新鏈表的尾部節點的next設為nullptr，結束鏈表return newhead; // 返回新鏈表的頭部}
};
3.遞歸
利用函數的棧來輔助完成反轉
基本思想是將原始鏈表的頭部節點不斷地移到新鏈表的尾部，從而實現鏈表的反轉。這個方法不需要額外的堆棧空間，但需要小心處理鏈表節點的指針。函數將遞歸地反轉鏈表，直到鏈表的末尾，然后返回新鏈表的頭部。
首先將問題拆為兩部分
1.反轉頭節點
2.反轉頭節點之外的所有節點
class Solution {
public:ListNode* reverseList(ListNode* head) {// 如果鏈表為空或只有一個節點，直接返回原鏈表if (!head || !head->next)return head;//反轉頭節點外的所有節點// 調用遞歸函數，將head->next作為新鏈表的頭部ListNode* newhead = reverseList(head->next);//反轉頭節點// 將head節點的下一個節點的下一個指針指向head，實現反轉head->next->next = head;// 將head節點的下一個指針設為nullptr，結束新鏈表的尾部head->next = nullptr;return newhead; // 返回新鏈表的頭部}
};
4.哈希表
可以用一個哈希表來儲存每個節點的前一個節點
class Solution {
public:ListNode* reverseList(ListNode* head) {// 如果鏈表為空或只有一個節點，直接返回原鏈表if (!head || !head->next)return head;unordered_map<ListNode*, ListNode*> hash; // 創建哈希表，存儲每個節點和它們的前一個節點ListNode* curr = head; // 當前節點// 構建哈希表while (curr->next) {hash.insert({curr->next, curr}); // 存儲當前節點的下一個節點和當前節點的映射關系curr = curr->next; // 移動到下一個節點}ListNode* newhead = curr; // 新鏈表的頭部為原始鏈表的末尾curr = newhead; // 重新將curr指向新鏈表的頭部// 根據哈希表中的映射關系重新連接節點的指針while (curr) {curr->next = hash[curr]; // 重新連接節點的next指針curr = curr->next; // 移動到下一個節點}head->next = nullptr; // 將原始鏈表的頭部的next設為nullptr，結束鏈表return newhead; // 返回新鏈表的頭部}
};
