# Code Random Recording Algorithm Camp DAY3 | 203. Remove Linked List Elements 707. Design Linked Lists 206. Reverse Linked Lists

explain: theoretical basis
Main points:
2. Linked list storage: the memory space is not continuous
3. Linked list definition: the js version is as follows

class ListNode {
val;
next = null;
constructor(value) {
this.val = value;
this.next = null;
}
}

4. Linked list operations: insert, delete, query

# 203. Remove linked list elements

Ideas:
1. Virtual head node: because the head node may be deleted, it needs to be set
2. If the value of next is equal, jump out of this cycle after deletion: because it is necessary to check whether the new next object is also equal to val
3. If not equal, then cur moves to the next node to continue checking cur.next

code:

var removeElements = function(head, val) {
let cur=ret;//Note that cur here is a linked list node
while(cur.next){//The access pointer method here is different from CPP, cpp is ->, and here is accessed as an object
if(cur.next.val===val){
cur.next=cur.next.next;
continue;//Need to check whether the updated value of cur.next is still equal to val
}
cur=cur.next;//cur update is equal to the next node
}
};

question:
1. What does the prototype in MyLinkedList.prototype.getNode in the code mean?
2. Does get return val or node?
Answer: I wrote two functions, one returns node and the other returns val. The function that returns node is convenient for other function calls later.
Complexity analysis:
Time complexity: O(n)

Ideas:
2. For the implementation of various methods, see notes for details. Note that a getnode function is defined for later calling.

• get(index): Get the value of the index node in the linked list. Returns -1 if the index is invalid. Here getnode is called, and the virtual head node is used in getnode.
• 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. Note that the processing of the tail node when adding a node to an empty list should also be equal to node.
• addAtTail(val): Append the node with value val to the last element of the linked list. Also pay attention to the processing of the head node when adding nodes to the empty 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. Classify and discuss according to the topic, and then call getnode to get the node of index-1.
• deleteAtIndex(index): If the index index is valid, delete the index-th node in the linked list. 1. First discuss the situation where the head node is deleted, that is, if(index === 0). In this case, if the tail node is deleted at the same time (it becomes an empty list after deletion), then the tail node must be equal to the head node The node is null. 2. What is deleted is not the head node, call getnode to get the element of index-1, and then change the value of next. Also pay attention to the case of deleting the tail node, the tail node needs to become the node of index-1.

code:

constructor(val, next) {
this.val = val;
this.next = next;
}
}

/**
* Initialize your data structure here.
* Singly linked list stores the head and tail nodes and the number of nodes
*/
this._size = 0;
this._tail = null;
};

/**
* Get the value of the index-th node in the linked list. If the index is invalid, return -1.
* @param {number} index
* @return {number}
*/
if(index < 0 || index >= this._size) return null;
// Create a virtual head node
while(index-- >= 0) {
cur = cur.next;
}
return cur;
};
if(index < 0 || index >= this._size) return -1;
// Get the current node
return this.getNode(index).val;
};

/**
* Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
* @param {number} val
* @return {void}
*/
this._size++;
if(!this._tail) {
this._tail = node;
}
};

/**
* Append a node of value val to the last element of the linked list.
* @param {number} val
* @return {void}
*/
const node = new LinkNode(val, null);
this._size++;
if(this._tail) {
this._tail.next = node;
this._tail = node;
return;
}
this._tail = node;
};

/**
* Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
* @param {number} index
* @param {number} val
* @return {void}
*/
if(index > this._size) return;
if(index <= 0) {
return;
}
if(index === this._size) {
return;
}
// Get the previous node of the target node
const node = this.getNode(index - 1);
this._size++;
};

/**
* Delete the index-th node in the linked list, if the index is valid.
* @param {number} index
* @return {void}
*/
if(index < 0 || index >= this._size) return;
if(index === 0) {
// If the deleted node is also a tail node, the tail node should be processed
if(index === this._size - 1){
}
this._size--;
return;
}
// Get the previous node of the target node
const node = this.getNode(index - 1);
node.next = node.next.next;
// Handle tail nodes
if(index === this._size - 1) {
this._tail = node;
}
this._size--;
};

question:
The idea is good, but in fact, the code I wrote has been debug ged for a long time, and I am not familiar with the js syntax. I don’t know the definition of js pointers and the writing of js classes and objects.

Ideas:
1. Double pointers actually need three pointers, pre, cur and temp respectively record three nodes.
2. Recursion. Two parameters, recursively update pre and head each time, and use temp to record before head.next changes.

code:

// Double pointer:
let temp = null, pre = null, cur = head;
while(cur) {
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
// temp = cur = null;
return pre;
};

// recursion:
var reverse = function(pre, head) {
return reverse(pre, temp);
}