【c++Leetcode】206. Reverse Linked List

问题入口

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;}