Yesterday, I went to the server and wanted to build a wordpress for fun. Now I’m waiting for the domain name to be put on record.

I’m going to continue to write lists today

Reverse linked List (Force Link No.206)

Self-written code:

ListNode* reverseList(ListNode* head) { ListNode* tmp_ptr = head; vector<int> tmp_vector = {}; while (tmp_ptr) { tmp_vector.push_back(tmp_ptr->val); tmp_ptr = tmp_ptr->next; } tmp_ptr = head; int index = tmp_vector.size() - 1; while (tmp_ptr) { if (! tmp_ptr->next) { tmp_ptr->val = tmp_vector[index]; tmp_ptr = tmp_ptr->next; } else { tmp_ptr->val = tmp_vector[index--]; tmp_ptr = tmp_ptr->next; } } return head; }Copy the code

Space complexity is high and a vector is created

Not using extra space (using temporary variables)

ListNode* reverseList(ListNode* head) { ListNode* new_head = nullptr; While (head) {ListNode* TMP = head->next; Head ->next = new_head; new_head = head; head = tmp; } return new_head; }Copy the code

Instead of creating new memory, use an extra header, reverse in place, and store extra temporary nodes in head->next.