Code Caprice Algorithm Training Camp Day 3 | 203. Remove Linked List Elements , 707. Design Linked Lists , 206. Reverse Linked Lists
Linked List Basics
Linked list node definition:
Single list
struct ListNode { int val; //Store elements on nodes ListNode *next; //pointer to the next node ListNode(int x) : val(x), next(nullptr) {} //node constructor };
Note: Although C++ will generate a constructor by default without writing this constructor, the constructor generated by C++ by default will not initialize any member variables!
The time complexity of adding and deleting the linked list is smaller than that of the array, which is O(1), but the premise of adding or deleting is to find the previous node of the operation node, and the time complexity of searching in the linked list is O(n).
Insertion/deletion (time complexity) | query (time complexity) | scenes to be used | |
---|---|---|---|
array | O(n) | O(1) | The amount of data is fixed, frequent queries, less additions and deletions |
linked list | O(1) | O(n) | The amount of data is not fixed, frequent additions and deletions, and fewer queries |
LeetCode 203 Remove Linked List Elements
Topic link: 203. Remove linked list elements
Idea: The removal operation of the linked list is to make the node next pointer directly point to the next node, but the original node still exists, and the memory needs to be released!
Due to the particularity of the linked list, when deleting the head node, there will be two processing methods:
- Use the original linked list directly to delete
- Set a virtual head node, and then delete
Method 1: directly use the original linked list to delete (directly move the head node backward one bit)
class Solution { public: ListNode* removeElements(ListNode* head, int val) { //delete head node while(head != NULL && head->val == val) { ListNode* tmp = head; head = head->next; delete tmp; } //remove non-head nodes ListNode* cur = head; while(cur != NULL && cur->next!= NULL) { if(cur->next->val == val) { ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; } else { cur = cur->next; } } return head; } };
Method 2: Set a virtual head node, and then perform a deletion operation (the same as other node operations)
class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); //Set up a virtual head node dummyHead->next = head; //Point the virtual head node to head, which is convenient for later operations ListNode* cur = dummtHead; while(cur->next != NULL) { if(cur->next->val == val) { ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; } else { cur = cur->next; } } head = dummyHead->next; delete dummyHead; return head; } };
Note: When using this method to return the head node, remember to return dummyNode->next;, this is the new head node
LeetCode 707 Question Design Linked List
Topic link: 707. Design Linked List
Implement these functions in the linked list class:
- get(index): Get the value of the index node in the linked list. Returns -1 if the index is invalid.
- addAtHead(val): Add a node with value val before the first element of the linked list. After insertion, the new node will be the first node of the linked list.
- addAtTail(val): Append the node with value val to the last element of the linked list.
- addAtIndex(index,val): Add a node with the value val before the index node in the linked list. If index is equal to the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length of the linked list, the node will not be inserted. If index is less than 0, insert the node at the head.
- deleteAtIndex(index): If the index index is valid, delete the index-th node in the linked list.
class MyLinkedList { public: //Define the linked list node structure struct LinkedNode { int val; LinkedNode* next; LinkedNode(int val):val(val),next(nullptr){} }; //Initialize linked list MyLinkedList() { _dummyHead = new LinkedNode(0); //Define the virtual head node here _size = 0; }; //Get the value of the index node, if the index is an illegal value, return -1 directly int get(int index) { if(index > (_size - 1) || index < 0) { return -1; } LinkedNode* cur = _dummyHead->next; while(index--) { cur = cur->next; } return cur->val; } //Add a node at the front of the linked list void addAtHead(int val) { LinkedNode* newNode = new LinkedNode(val); newNode->next = _dummyHead->next; _dummyHead->next = newNode; _size++; } //Add a node at the end of the linked list void addAtTail(int val) { LinkedNode* newNode = new LinkedNode(val); LinkedNode* cur = _dummyHead; while(cur->next != nullptr) { cur = cur->next; } cur->next = newNode; _size++; } // Insert a new node before the index-th node, for example, if the index is 0, then the newly inserted node is the new head node of the linked list. // If index is equal to the length of the linked list, it means that the newly inserted node is the tail node of the linked list // If index is greater than the length of the linked list, return empty // If index is less than 0, insert the node at the head void addAtIndex(int index, int val) { if(index > _size) return; if(index < 0) index = 0; LinkedNode* newNode = new LinkedNode(val); LinkedNode* cur = _dummyHead; while(index--) { cur = cur->next; } newNode->next = cur->next; cur->next = newNode; _size++; } //Delete the index node, if the index is greater than the length of the linked list, return directly, the index starts from 0 void deleteAtIndex(int index) { if(index >= _size || index < 0) return; LinkedNode* cur = _dummyHead; while(index--) { cur = cur->next; } LinkedNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; _size--; } private: int _size; LinkedNode* _dummyHead; };
LeetCode 206 question reverse linked list
Topic link: 206. Reverse Linked List
Idea: Define a cur pointer to point to the head node, define a pre pointer to initialize to null, use tmp to continuously save cur->next, then cur->next points to pre, and pre moves backward until cur points to NULL.
double pointer method
class Solution { public: ListNode* reverseList(ListNode* head) { ListNode* temp; ListNode* cur = head; ListNode* pre = NULL; while(cur) { temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; } };
recursive method
class Solution { public: ListNode* reverse(ListNode* pre, ListNode* cur) { if(cur == NULL) return pre; ListNode* temp = cur->next; cur->next = pre; return reverse(cur,temp); } ListNode* reverseList(ListNode* head) { return reverse(NULL, head); } };
Flip pointer from back to front
class Solution { public: ListNode* reverseList(ListNode* head) { // edge condition judgment if(head == NULL) return NULL; if(head->next == NULL) return head; // Recursive call, flip the linked list starting from the second node ListNode *last = reverseList(head->next); // Flip the direction of the head node and the second node head->next->next = head; // At this time, the head node is the tail node, and next points to NULL head->next = NULL; return last; } };