Code Caprice Algorithm Training Camp Day 3 | 203. Remove Linked List Elements , 707. Design Linked Lists , 206. Reverse Linked Lists

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
arrayO(n)O(1)The amount of data is fixed, frequent queries, less additions and deletions
linked listO(1)O(n)The amount of data is not fixed, frequent additions and deletions, and fewer queries

LeetCode 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:

1. Use the original linked list directly to delete
2. 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 tmp;
}

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

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) {
while(cur->next != NULL) {
if(cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
}
else {
cur = cur->next;
}
}
}
};
```

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

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

_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;
}
while(index--) {
cur = cur->next;
}
return cur->val;
}

_size++;
}

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;
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;
while(index--) {
cur = cur->next;
}
cur->next = cur->next->next;
delete tmp;
_size--;
}
private:
int _size;
};
```

LeetCode 206 question 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* temp;
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);
}
}
};
```

Flip pointer from back to front

```class Solution {
public:
// edge condition judgment