（一）需要

最近开始学习算法，链表是数据结构中蛮经典的一个数据结构。而单链表是根底中的根底。

（二）单链表

1、定义

单链表中的每个结点不仅蕴含值，还蕴含链接到下一个结点的援用字段。通过这种形式，单链表将所有结点按程序组织起来。

// Definition for singly-linked list.public class SinglyListNode {    int val;    SinglyListNode next;    SinglyListNode(int x) { val = x; }}

在大多数状况下，咱们将应用头结点(第一个结点)来示意整个列表。

与数组不同，咱们无奈在常量工夫内拜访单链表中的随机元素。 如果咱们想要取得第 i 个元素，咱们必须从头结点一一遍历。 咱们按索引来拜访元素均匀要花费 O(N) 工夫，其中 N 是链表的长度。

2、操作

（1）增加操作

  • 应用给定值初始化新结点 cur；
  • 将 cur 的 next 字段链接到 prev 的下一个结点 next ；
  • 将 prev 中的 next 字段链接到 cur 。

（2）删除操作

3、设计链表

设计链表的实现。您能够抉择应用单链表或双链表。单链表中的节点应该具备两个属性：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 个节点。
实现的代码如下：
var MyLinkedList = function() {  this.head=null  this.length=0};/** 获取链表中第 index 个节点的值。如果索引有效，则返回-1。 * @param {number} index * @return {number} */MyLinkedList.prototype.get = function(index) {  //留神：这里须要有index 等于长度的判断  if(index < 0 || index >= this.length){    return -1  }  let cur=this.head;  let sum=0;  if(index == 0){    return cur.val  }else{    while(sum<index){      cur=cur.next;      sum++    }    return cur.val  }};/** 在链表的第一个元素之前增加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。 * @param {number} val * @return {void} */MyLinkedList.prototype.addAtHead = function(val) {  //头节点不存在  if(!this.head){    this.head={val,next:null}  }else{    //头节点存在    let node={val,next:this.head}    this.head=node  }  this.length++};/** 将值为 val 的节点追加到链表的最初一个元素。 * @param {number} val * @return {void} */MyLinkedList.prototype.addAtTail = function(val) {  let node={val,next:null}  //头节点不存在  if(!this.head){    this.head=node  }else{    //找到倒数第二个节点    let cur=this.head    while(cur.next){      cur=cur.next    }    cur.next=node  }  this.length++};/** 在链表中的第 index 个节点之前增加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的开端。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。 * @param {number} index  * @param {number} val * @return {void} */MyLinkedList.prototype.addAtIndex = function(index, val) {  //超过长度就return   if (index < 0 || index > this.length){    return   }  let node = { val, next: null };  let cur = this.head,    pre,    sum = 0;  if (index === 0) {    return this.addAtHead(val); //index为0， 头部插入  } else if (index === this.length) {    return this.addAtTail(val); //index = length，在开端进行追加  } else {    while (sum <= index - 1) {      //找到index地位的前一个节点      pre = cur;       cur = cur.next; //下一个节点      sum++;    }    pre.next = node;    node.next = cur;  }  this.length++};/** 如果索引 index 无效，则删除链表中的第 index 个节点。 * @param {number} index * @return {void} */MyLinkedList.prototype.deleteAtIndex = function(index) {  if (index < 0 || index >= this.length) return;  let cur = this.head,    pre,    countIndex = 0;  if (index === 0){    this.head = cur.next  }else{    //let sum=0    //while(sum<index-1){      //找到删除地位的前一个节点      //pre=cur      //cur=cur.next      //sum++    //}    while (countIndex++ < index) {      //找到删除地位的前一个节点      pre = cur;      cur = cur.next;    }    if (cur) {      //间接链接到删除地位的下一个节点      pre.next = cur.next;    } else {      pre.next = null;    }  }  this.length--};/** * 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) */

以上

参考链接

Leecode

https://leetcode-cn.com/leetb...

写在最初的话

学习路上，经常会懈怠

《有想学技术须要监督的同学嘛~》
https://mp.weixin.qq.com/s/Fy...