203.移除链表元素
题目链接：
https://leetcode.cn/problems/remove-linked-list-elements/
题目描述：
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
思路：
定义一个节点root，其next为链表的head。定义游标cur从root开始，沿链表进行遍历，判断cur.next.val的值是否等于val，如果相等说明cur.next为需要删除的节点。删除方法为cur.next = cur.next.next，注意这里cur.next不能为undefined，所以循环的条件为cur.next为真值。
代码：
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} val
* @return {ListNode}
*/
var removeElements = function(head, val) {
let root = new ListNode(0,head)
let cur = root
while(cur.next){
if(cur.next.val === val){
if(!cur.next.next){
cur.next = null
return root.next
}
else{
cur.next = cur.next.next
}
}
else{
cur = cur.next
}
}
return root.next
};
206.反转链表
题目链接：
https://leetcode.cn/problems/reverse-linked-list/
题目描述：
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
思路：
可以使用递归、迭代的方式，上一题利用了迭代的方式，这一题采用递归的方法。反转的过程可以分解为把head之后的链表反转，再把head放到其末尾。递归的终止条件为链表没元素或者只有一个元素。
代码：
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if(!head){
return null
}
if(!head.next){
return head
}
let newHead = reverseList(head.next)
head.next.next =head
head.next = null
return newHead
};
707.设计链表
题目链接：
https://leetcode.cn/problems/design-linked-list/
题目描述：
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能：
-
get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
-
addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
-
addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
-
addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
-
deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
思路：
需要设计的链表操作有：从头部加节点、从尾部加节点、特定位置增加节点、特定位置删除节点、获取特定位置的节点储存的值。只设计一个纯粹的包含哨兵节点的单向链表，每个节点只有val和next属性，不保存计算链表的长度。
做题时最好控制不同操作遍历链表的思路一致从而避免混乱。我这种解法都是从哨兵节点开始遍历，当前遍历节点的下一个节点为对应的需要处理的节点，如果遍历次数未达到所需的次数时下一个节点为空则判断输入不合法。
代码：
var MyLinkedList = function() {
this.root={
val: Infinity,
next: null
}
};
/**
* @param {number} index
* @return {number}
*/
MyLinkedList.prototype.get = function(index) {
let cur = this.root
for(let i = 0; i < index; i++){
if(!cur.next){
return -1
}
cur = cur.next
}
return cur.next ? cur.next.val : -1
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtHead = function(val) {
let cur = this.root.next
let newNode = {
val: val,
next: this.root.next
}
this.root.next = newNode
};
/**
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtTail = function(val) {
let cur = this.root
while(cur.next){
cur = cur.next
}
cur.next = {
val: val,
next: null
}
};
/**
* @param {number} index
* @param {number} val
* @return {void}
*/
MyLinkedList.prototype.addAtIndex = function(index, val) {
if(index < 0){
this.addAtHead(val)
}
let cur = this.root
for(let i = 0; i < index; i++){
if(!cur.next){
return
}
cur = cur.next
}
let newNode = {
val: val,
next: cur.next
}
cur.next = newNode
};
/**
* @param {number} index
* @return {void}
*/
MyLinkedList.prototype.deleteAtIndex = function(index) {
let cur = this.root
for(let i = 0; i < index; i++){
if(!cur.next){
return
}
cur = cur.next
}
cur.next = cur.next?.next
};