前言🌧️
算法，对前端人来说陌生又熟悉，很多时候我们都不会像后端工程师一样重视这项能力。但事实上，算法对每一个程序员来说，都有着不可撼动的地位。
因为开发的过程就是把实际问题转换成计算机可识别的指令，也就是《数据结构》里说的，「设计出数据结构，在施加以算法就行了」。
当然，学习也是有侧重点的，作为前端我们不需要像后端开发一样对算法全盘掌握，有些比较偏、不实用的类型和解法，只要稍做了解即可。
题目🦀
707. 设计链表
难度中等
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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值都在[1, 1000]之内。 - 操作次数将在
[1, 1000]之内。 - 请不要使用内置的 LinkedList 库。
解题思路🌵
什么是链表，链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
- 创建一个额外的方法getNode方便操作，
解题步骤🐂
- 直接使用原来的链表来进行操作。
- 设置一个虚拟头结点在进行操作。
源码🔥
class LinkNode{ constructor(val,next){ this.val=val; this.next=next; } } var MyLinkedList = function() { this._size=0; this._tail=null; this._head=null; }; /** * @param {number} index * @return {number} */ MyLinkedList.prototype.getNode = function(index) { if(index<0||index>=this._size){return null}; //创建虚拟头节点 let cur = new LinkNode(0,this._head); while(index>=0){ cur=cur.next index-- } return cur }; /** * @param {number} index * @return {number} */ MyLinkedList.prototype.get = function(index) { if(index<0||index>=this._size){return -1}; //获取当前节点 return this.getNode(index).val; }; /** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtHead = function(val) { const node = new LinkNode(val,this._head) this._head=node; this._size++; if(!this._tail){ this._tail=node } }; /** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtTail = function(val) { const node = new LinkNode(val,null); this._size++; if(this._tail){ this._tail.next=node; this._tail = node; return } this._tail=node; this._head=node; }; /** * @param {number} index * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtIndex = function(index, val) { if(index>this._size){return;} if(index<=0){ this.addAtHead(val) return } if(index===this._size){ this.addAtTail(val) return } //获取目标节点的上一个节点 const node = this.getNode(index-1); node.next=new LinkNode(val,node.next); this._size++; }; /** * @param {number} index * @return {void} */ MyLinkedList.prototype.deleteAtIndex = function(index) { if(index < 0 || index >= this._size){return} if(index === 0){ this._head=this._head.next; //如果删除的这个节点同时是尾节点,需要处理 if(index===this._size-1){ this._tail=null } this._size--; return } //获取目标节点的上一个节点 const node =this.getNode(index-1) node.next = node.next.next //处理尾节点 if(index === this._size -1){ this._tail = node } this._size--; return }; /** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */
结束语🌞
那么鱼鱼的LeetCode算法篇的「LeetCode」707-设计链表⚡️就结束了，算法这个东西没有捷径，只能多写多练，多总结，文章的目的其实很简单，就是督促自己去完成算法练习并总结和输出，菜不菜不重要，但是热爱🔥，喜欢大家能够喜欢我的短文，也希望通过文章认识更多志同道合的朋友，如果你也喜欢折腾，欢迎加我好友，一起沙雕，一起进步。
