問題入口

time complexity: O(n), space complexity:O(1)

ListNode* reverseList(ListNode* head) {ListNode* prev = nullptr;ListNode* curr = head;while(curr){ListNode* forward = curr->next;curr->next = prev;prev = curr;curr = forward;}return prev;
}

time complexity: O(n), space complexity:O(n)

ListNode* reverseList(ListNode* head) {if(head == NULL || head->next == NULL) return head;ListNode* tail = reverseList3(head->next);head->next->next = head;head->next = nullptr;return tail;}

要計算給定“reverseList”函數的空間復雜度，讓我們分析內存使用情況：
1.函數調用堆棧：
-該函數是遞歸的，每次遞歸調用都會向調用堆棧添加一個新幀。
-遞歸的深度取決于鏈表的長度。
-在每個遞歸級別，函數都使用常量空間（局部變量：“tail”、“head”）。
-因此，調用堆棧貢獻的空間復雜度是O（n），其中n是鏈表的長度。
2.局部變量（`tail`，`head`）：
-該函數為每個遞歸級別使用兩個本地指針（“tail”和“head”）。
-這些變量所使用的空間在每個級別上都是恒定的。
-由于遞歸的深度是O（n），因此這些變量貢獻的空間復雜度也是O（n）。
3.總體空間復雜性：
-空間復雜性的主要因素是遞歸導致的調用堆棧。
-因此，“reverseList3”函數的總體空間復雜度為O（n），其中n是鏈表的長度。
總之，由于遞歸調用堆棧，空間復雜度為O（n）。每個級別的遞歸都貢獻了恒定的空間，但級別的數量與鏈表的長度成比例。

待完成

ListNode* reverseList(ListNode* head) {if(head!= nullptr)//head->next!= NULL occurs member access within null pointer of type 'ListNode' ... {   ListNode* tail_to_head = head;while(tail_to_head->next != nullptr )tail_to_head = tail_to_head->next;ListNode* temp = tail_to_head;for (ListNode* current = head; head != temp ; current = head){while(current->next != temp)current = current->next;temp->next = current;temp = temp->next;}head->next = nullptr;return tail_to_head;}return nullptr;}