203. Removing Chained Table Elements
Given the head node of a linked table and an integer val, delete all nodes in the table that satisfy == val and return the new head node.
Example 1:
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Example 2:
Input: head = [], val = 1
Output: []
Example 3:
Input: head = [7,7,7,7], val = 7
Output: []
Tip:
The number of nodes in the list is in the range [0, 104] Inside.
1 <= <= 50
0 <= val <= 50
The correct solution (... . whateverthisis)
Thought 1:
Thought two:
These are the two ways of thinking about this AC question, nothing much to say, it's easy to understand;
Chained Table Preliminaries
Upcode (●'◡'●)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val.
* ListNode *next.
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* }
*/
class Solution {// First thought
public.
ListNode* removeElements(ListNode* head, int val) {
while(head!=NULL&&head->val==val){// Handle the case of removing the head node (note while, not if)
ListNode* tmp=head;// pointer tmp to head node
head=head->next;//head node move back
delete tmp;//free memory
}
ListNode* cur=head;//node currently being processed
while(cur!=NULL&&cur->next!=NULL){//Delete point
if(cur->next->val==val){
ListNode* tmp=cur->next;
cur->next=cur->next->next;
delete tmp; }
}
else{
cur=cur->next;//next point without deletion
}
}
return head;//returns the chained table
}
};//end scattering flowers ヾ(≧▽≦*)o
707. Designing Chained Tables
You can choose to design and implement your own chained tables using either single or double linked tables.
A node in a singly linked table should have two attributes: val and next. val is the value of the current node and next is a pointer/reference to the next node.
In the case of a bi-directional chained table, the attribute prev is also required to indicate the previous node in the chained table. It is assumed that all nodes in the chain table start with a subscript of 0.
Implements the MyLinkedList class:
MyLinkedList() Initializes the MyLinkedList object.
int get(int index) Gets the value of the node in the linked table whose subscript is index. If the subscript is invalid, -1 is returned.
void addAtHead(int val) Inserts a node with the value val before the first element in the chain table. After the insertion is complete, the new node becomes the first node in the chain table.
void addAtTail(int val) Appends a node with the value val as the last element in the chain table.
void addAtIndex(int index, int val) Inserts a node with the value val before the node in the chain table whose subscript is index. If index is equal to the length of the chain, then the node is appended to the end of the chain. If index is greater than the length, the node will not be inserted.
void deleteAtIndex(int index) Deletes the node in the chain table whose subscript is index if the subscript is valid.
Example:
Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output.
[null, null, null, null, 2, null, 3]
Explanation
MyLinkedList myLinkedList = new MyLinkedList();
(1);
(3);
(1, 2); // the linked list becomes 1->2->3
(1); // return 2
(1); // Now the chain table becomes 1->3
(1); // returns 3
Tip:
0 <= index, val <= 1000
Do not use the built-in LinkedList library.
The number of calls to get, addAtHead, addAtTail, addAtIndex, and deleteAtIndex should not exceed 2000.
The title is still well understood;
This question requires a "dummyhead" node;
That is, add another empty node before the real header node;
It may seem redundant, but it actually facilitates operations such as deleting nodes;
Upcode (●'◡'●)
class MyLinkedList {
public:
struct LinkedNode {//Defining a Chained Table
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}//constructor
};
MyLinkedList() {//Two variables are declared at the end of the program
_dummyHead = new LinkedNode(0);
_size = 0;
}
int get(int index) {
if (index > (_size - 1) || index < 0) {//illegitimate subscript
return -1;
}
LinkedNode* cur = _dummyHead->next;
while(index--){//O(index)consult (a document etc)
cur = cur->next;
}
return cur->val;//Return results
}
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;//existdummyheadand the real head node to insert elements between
_size++;
}
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(cur->next != nullptr){//Loop to the end of the chain table
cur = cur->next;
}
cur->next = newNode;//stick
_size++;
}
void addAtIndex(int index, int val) {
if(index > _size) return;//illegitimate subscript
if(index < 0) index = 0;//Pre-processing of special cases
LinkedNode* newNode = new LinkedNode(val);//new node
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur->next;
}
newNode->next = cur->next;//stick
cur->next = newNode;//update
_size++;
}
void deleteAtIndex(int index) {
if (index >= _size || index < 0) {//illegitimate subscript
return;
}
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur ->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;//Delete nodes
delete tmp;//Free up memory space（not essential）
_size--;
}
};//lit. finish and scatter flowersヾ(≧▽≦*)o
206. Reverse Chained Tables
Given the head node of a single linked table, reverse the table and return the reversed table.
Example 1:
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2]
Output: [2,1]
Example 3:
Input: head = []
Output: []
Tip:
The number of nodes in the chain table ranges from [0, 5000]
-5000 <= <= 5000
Positive solution (double pointer)
First define a cur pointer, pointing to the head node, and a pre pointer, initialized to null.
Then it's time to start reversing, first by saving the cur->next node with the tmp pointer, that is, by saving the node.
Why save this node? Because we're going to change the pointing of cur->next to point cur->next to pre, which has already reversed the first node.
Next, it's time to loop through the logic of the following code, continuing to move the pre and cur pointers.
Finally, the cur pointer has pointed to null, the loop is over, and the chain table has been reversed. At this point, we can just return the pre pointer, which points to the new head node.
Upcode (●'◡'●)
class Solution {
public.
ListNode* reverseList(ListNode* head) {
ListNode* temp; // save the next node of cur
ListNode* cur = head;
ListNode* pre = NULL; while(cur) { ListNode* temp; // hold cur's next node.
while(cur) {
temp = cur->next; // save the next node of cur, because cur->next will be changed next.
cur->next = pre; // Flip the operation.
// Update the pre and cur pointers
pre = cur; cur = temp; // update pre and cur pointers.
cur = temp; }
}
cur = temp; }
}
};//Ending ヾ(≧▽≦*)o
-Time Complexity\(O(n)\)
-Space complexity\(O(1)\)
One of the easier questions
It's not easy to write a blog, so please give me some support 8~!