第 115 题：写一个单向链数据结构的 js 实现并标注复杂度

[yygmind]

No description provided.

[lvwxx]

详解

class LinkList {
  constructor() {
    this.head = null
  }

  find(value) {
    let curNode = this.head
    while (curNode.value !== value) {
      curNode = curNode.next
    }
    return curNode
  }

  findPrev(value) {
    let curNode = this.head
    while (curNode.next!==null && curNode.next.value !== value) {
      curNode = curNode.next
    }
    return curNode
  }

  insert(newValue, value) {
    const newNode = new Node(newValue)
    const curNode = this.find(value)
    newNode.next = curNode.next
    curNode.next = newNode
  }

  delete(value) {
    const preNode = this.findPrev(value)
    const curNode = preNode.next
    preNode.next = preNode.next.next
    return curNode
  }
}

class Node {
  constructor(value, next) {
    this.value = value
    this.next = null
  }
}

[kvchen95]

问题来了，在哪学数据结构相关知识

[raul-taurus]

class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class SinglyLinkedList {

    #firstNode;

    constructor() {
        this.#firstNode = null;
    }

    get firstNode() {
        return this.#firstNode;
    }

    insertAfter(node, newNode) {
        if (!newNode) return;

        if (node) {
            newNode.next = node.next;
            node.next = newNode;
        }
        else {
            newNode.next = this.#firstNode;
            this.#firstNode = newNode;
        }
    }

    insertBeginning(newNode) {
        this.insertAfter(null, newNode);
    }

    removeAfter(node) {
        if (node) {
            node.next = node.next.next;
        }
        else if (this.#firstNode) {
            this.#firstNode = this.#firstNode.next;
        }
    }

    removeBeginning() {
        this.removeAfter(null);
    }
}

var list = new SinglyLinkedList();
list.insertBeginning(new Node("a"));
list.insertAfter(list.firstNode, new Node("d"));
list.insertAfter(list.firstNode, new Node("c"));
list.insertAfter(list.firstNode, new Node("b"));

var currentNode = list.firstNode;
while (currentNode) {
    console.log(currentNode.data);
    currentNode = currentNode.next;
}

list.removeBeginning(); // Remove 'a'
list.removeAfter(list.firstNode); // Remove 'c' after 'b'

var currentNode = list.firstNode;
while (currentNode) {
    console.log(currentNode.data);
    currentNode = currentNode.next;
}

[ZodiacSyndicate]

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

class LinkedList {
    head = null
    tail = null
    size = 0

    // 时间复杂度O(n)
    get = index => {
        if (index < 0) return -1
        let node = this.head
        for (let i = 0; i < index; i++) {
            if (!node) return -1
            node = node.next
        }
        return node ? node.val : -1
    }

    // 时间复杂度O(1)
    addAtHead = val => {
        const node = new ListNode(val)
        if (!this.head) {
            this.head = this.tail = node
        } else {
            node.next = this.head
            this.head = node
        }
        this.size++
    }

    // 时间复杂度O(1)
    addAtTail = val => {
        const node = new ListNode(val)
        if (!this.tail) {
            this.head = this.tail = node
        } else {
            this.tail.next = node
            this.tail = node
        }
        this.size++
    }

    // 时间复杂度O(n)
    addAtIndex = (index, val) => {
        const node = new ListNode(val)
        if (index > this.size) return
        if (index === this.size) return this.addAtTail(val)
        if (index <= 0) return this.addAtHead(val)
        let head = this.head
        for (let i = 1; i < index; i++) {
            if (!head) return
            head = head.next
        }
        node.next = head.next
        head.next = node
        this.size++
    }

    // 时间复杂度O(n)
    deleteAtIndex = index => {
        let head = this.head
        if (!head || index >= this.size || index < 0) return
        if (index === 0) {
            if (this.size === 1) {
                this.head = this.tail = null
            } else {
                this.head = this.head.next
            }
            this.size--
            return
        }
        for (let i = 1; i < index; i++) {
            if (!head) return
            head = head.next
        }
        if (!head) return
        if (head.next) {
            if (head.next === this.tail) {
                this.tail = head
                head.next = null
            } else {
                head.next = head.next.next
            }
        } else {
            this.head = this.tail = null
        }
        this.size--
    }
}

[xiaokeqi]

class Node {
	constructor(value,next) {
	    this.value = value;
	    this.next = next;
	}
}
class LinkList {
  constructor(value) {
      this.head = new Node(value);
  }
  add(newVal, val) {
      const newNode = new Node(newVal);
      const curNode = this.find(val);
      newNode.next = curNode.next;
      curNode.next = newNode;
    return newNode;
  }
  // 时间复杂度O(n)
  find(value){
      let curNode = this.head;
      while(curNode.value != value && curNode) {
        curNode = curNode.next ? curNode.next : null;
      }
    return curNode;
  }
  del(val) {
    let prevNode = this.findPrev(val);
    let curNode = prevNode.next;
    prevNode.next = curNode.next;
    return curNode;
    
  }
  findPrev(val) {
    let curNode = this.head;
    while(curNode && curNode.next && curNode.next.value !== val ) {
        curNode = curNode.next ? curNode.next : null;
    }
    return curNode;
  }
  print() {
    let curNode = this.head;
    while(curNode){
      console.log(curNode.value);
      curNode = curNode.next;
    }
  }
}

const link = new LinkList('11');
link.add('22','11');
link.add('33','22');
link.del('22');
link.print();

[ZodiacSyndicate]

class Node {
	constructor(value,next) {
	    this.value = value;
	    this.next = next;
	}
}
class LinkList {
  constructor(value) {
      this.head = new Node(value);
  }
  add(newVal, val) {
      const newNode = new Node(newVal);
      const curNode = this.find(val);
      newNode.next = curNode.next;
      curNode.next = newNode;
    return newNode;
  }
  // 时间复杂度O(n)
  find(value){
      let curNode = this.head;
      while(curNode.value != value && curNode) {
        curNode = curNode.next ? curNode.next : null;
      }
    return curNode;
  }
  del(val) {
    let prevNode = this.findPrev(val);
    let curNode = prevNode.next;
    prevNode.next = curNode.next;
    return curNode;
    
  }
  findPrev(val) {
    let curNode = this.head;
    while(curNode && curNode.next && curNode.next.value !== val ) {
        curNode = curNode.next ? curNode.next : null;
    }
    return curNode;
  }
  print() {
    let curNode = this.head;
    while(curNode){
      console.log(curNode.value);
      curNode = curNode.next;
    }
  }
}

const link = new LinkList('11');
link.add('22','11');
link.add('33','22');
link.del('21');
link.print();

我删除node的时候假如把head传进去，这个方法就不对了

[weiweixuan]

神仙题，，，看不懂咋办

[liuwenai]

//链表节点
class Node {
constructor(element) {
this.element = element
this.next = null
}
}

//链表
class LinkedList {
constructor() {
this.head = null
this.length = 0
}

//追加元素
append(element) {
    const node = new Node(element)
    let current = null
    if (this.head === null) {
        this.head = node
    } else {
        current = this.head
        while (current.next) {
            current = current.next
        }
        current.next = node
    }
    this.length++
}

//任意位置插元素
insert(position, element) {
    if (position >= 0 && position <= this.length) {
        const node = new Node(element)
        let current = this.head
        let previous = null
        let index = 0
        if (position === 0) {
            this.head = node
        } else {
            while (index++ < position) {
                previous = current
                current = current.next
            }
            node.next = current
            previous.next = node
        }
        this.length++
        return true
    }
    return false
}

//移除指定位置元素
removeAt(position) {
    //检查越界
    if (position > -1 && position < length) {
        let current = this.head
        let previous = null
        let index = 0
        if(position === 0){
            this.head = current.next
        }else{
            while(index++ < position){
               previous = current
               current = current.next
            }
            previous.next = current.next
        }
        this.length--
        return current.element
    }
    return null
}

//寻找元素下标
findIndex(element){
    let current = this.head
    let index = -1
    while(current){
        if (element === current.element){
            return index + 1
        }
        index++
        current = current.next
    }
    return -1
}

//删除指定文档
remove(element){
    const index = this.indexOf(element)
    return this.removeAt(index)
}

isEmpty(){
    return !this.length
}

size(){
    return this.length
}

//转为字符串
toString(){
    let current = this.head
    let string = ''
    while(current){
        string += '$(current.element)'
        current = current.next
    }
    return string
}

}

正好学习的时候照着写过，不过时间复杂度和空间复杂度我都不太懂💔

[daolou]

神仙题，，，看不懂咋办

那就多学呗，#156 (comment)

[ghost]

看不懂，从哪学习这些链表啥的基础知识

[lvwxx]

看不懂，从哪学习这些链表啥的基础知识

lvwxx/blog#1 (comment)

[jdkwky]

class Node {
constructor(value, next) {
this.value = value;
this.next = next;
}
}

class LinkList {
constructor(value) {
const node = new Node(value, null);
this.linkList = node;
this.currentNode = node;
}

_delete(value, node, preNode) {
    const currentValue = node.value;
    const nextNode = node.next;
    if (currentValue === value) {
        if (nextNode) {
            preNode.next = nextNode;
        } else {
            preNode.next = null;
        }
    } else {
        if (node.next) {
            this._delete(value, node.next, node);
        }
    }
}

insert(value) {
    // o(1)
    const nextNode = new Node(value, null);
    this.currentNode.next = nextNode;
    this.currentNode = nextNode;
    return this;
}

delete(value) {
    // O(n)
    if (this.linkList.next) {
        if (this.linkList.value === value) {
            this.linkList = this.linkList.next;
        } else {
            this._delete(value, this.linkList.next, this.linkList);
        }
    } else {
        if (value === this.linkList.value) {
            this.linkList = new Node(null, null);
        }
    }
    return this;
}
_findNode(value, node) {
    if (node.value == value) {
        return node;
    } else {
        const nextNode = node.next;
        if (nextNode) {
            return this._findNode(value, nextNode);
        }
        return null;
    }
}
findNode(value) {
    return this._findNode(value, this.linkList);
}
getNode() {
    return this.linkList;
}

}

[lhyt]

常规的解法就是增删改查，修改next的指向和value值或者删除增加节点。这里不再走寻常路。维护一个数组，通过代理数组操作返回链表。数组<item, index, array>型的api基本都是O(n)时间复杂度和O(1)空间复杂度，但是这里最后会有一个全部遍历同步的操作，额外稳定增加O(n)时间复杂度。如果想做到O(1)复杂度的修改，则需要劫持每一个数组操作，并利用额外缓存存下各种信息，大约还需要O(n)空间复杂度才能换取O(1)的时间复杂度

class LinkList {
  constructor(...args) {
    this.temp = []
    this.temp.push(...args)
  }
}

function createLinkList(...init) {
  const ret = new LinkList(...init)
  let current
  const result = ret.temp.reduce((res, cur) => {
    current = current || res
    current.value = cur
    current.next = current.next || {}
    current = current.next
    return res
  }, Object.create(new Proxy(ret.temp, {
    get(target, name) {
      const record = Reflect.get(target, name)
      if (typeof record === 'function') {
        return (...args) => {
          const retVal = Reflect.apply(record, target, args)
          let current = result
          ret.temp.forEach(item => {
            current.value = item
            current = current.next || {}
          })
          return retVal
        }
      }
      return record
    }
  })))
  return result
}

const mockLinkList = createLinkList(1,2,3)
mockLinkList.push(1, 2)
mockLinkList.pop()
// ......所有的数组操作

[gto999]

const head = Symbol('head');

class LinkListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkList {
    constructor() {
        this[head] = null;
    }
    add(data) {
        const newNode = new LinkListNode(data);
        if (this[head] === null) {
            this[head] = newNode;
        } else {
            let current = this[head];
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }
    insertBefore(data, index) {
        const newNode = new LinkListNode(data);

        if (this[head] === null) {
            throw new RangeError(`index ${index} does not exist in this list`);
        }

        if (index == 0) {
            newNode.next = this[head];
            this[head] = newNode;
        } else {

            let current = this[head],
                previous = null;
            let i = 0;

            while (current.next !== null && i < index) {
                previous = current;
                current = current.next;
                i++;
            }

            if (i < index) {
                throw new RangeError(`index ${index} does not exist in the list`);
            }

            previous.next = newNode;
            newNode.next = current;
        }
    }
    insertAfter(data, index) {
        const newNode = new LinkListNode(data);

        if (this[head] === null) {
            throw new RangeError(`index ${index} does not exist in the list`);
        }

        let current = this[head];

        let i = 0;

        while (current != null && i < index) {
            current = current.next;
            i++;
        }

        if (i < index) {
            throw new RangeError(`index ${index} does not exist in the list`);
        }

        newNode.next = current.next;
        current.next = newNode;
    }
    get(index) {
        if (index > -1) {
            let current = this[head];
            let i = 0;
            while (current != null && i < index) {
                current.next = currnt;
                i++;
            }
            return current !== null ? current.data : undefined;
        } else {
            return undefined;
        }
    }
    indexOf(data) {
        let current = this[head];
        let index = 0;

        while (current !== null) {
            if (current.data === data) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;;
    }

    remove(index) {
        if (this[head] === null || index < 0) {
            throw new RangeError(`index ${index} does not exist in the list`);
        }
        if (index === 0) {
            const data = this[head].data;
            this[head] = this[head].next;
            return data;
        }
        let currnet = this[head];
        let previous = null;
        let i = 0;

        while (currnet !== null && i < index) {
            previous = currnet;
            currnet = currnet.next;
            i++;
        }
        if (currnet !== null) {
            previous.next = currnet.next;
            return currnet.data;
        }

        throw new RangeError(`index ${index} does not exist in the list`);
    }

    clear() {
        this[head] = null;
    }

    get size() {
        if (this[head] === null) {
            return 0;
        }

        let current = this[head];
        let count = 0;
        while (current != null) {
            current = current.next;
            count++;
        }
        return count;
    }
    /**
     * The default iterator for the class.
     * @returns {Iterator} An iterator for the class.
     */
    [Symbol.iterator]() {
        return this.values();
    }
    /**
     * Create an iterator that returns each node in the list.
     * @returns {Iterator} An iterator on the list.
     */
    *values() {
        let current = this[head];

        while (current !== null) {
            yield current.data;
            currnet = current.next;
        }
    }
    /**
    * Converts the list into a string representation.
    * @returns {String} A string representation of the list.
    */
    toString() {
        return [...this].toString();
    }
}

[hugeorange]

 /**
    单向链表

    链表：由多个节点构成，每个节点包含自身数据和指向下个节点的引用
         物理上可以不连续但逻辑上必须连续（不一定是一块连续的内存）

    链表是一种常见的基础数据结构，是一种线性表，但是不会按线性的顺序存储数据而是每个节点存指向下个节点的引用
 */
class LinkNode {
    constructor(val) {
        if (val === void 0) throw new Error('请输入链表节点值')
        this.node = val
        this.next = null
    }
}

class LinkList {
    head = null
    size = 0

    // 有没有初始化的方法呢 ？？？
    initLinkedList() {}

    /**
    * @description: 根据索引获取 node，从头部遍历
    * @param {index} 
    * @return: linkNode
    */
    findNode(index) {
        if (index < 0 || index >= this.size || this.size == 0) return null
        let node = this.head
        for (let i=0; i<index; i++) {
            if (!node) return null
            node = node.next
        }
        return node ? node : null
    }
    
    // 时间复杂度 O(n)
    get(index) {
        return this.findNode(index)
    }

    // 时间复杂度 O(n)
    push(val) {
        const node = new LinkNode(val)
        if (!this.head) {
            this.head = node
        } else {
            let tail = this.findNode(this.size - 1)
            tail.next = node
        }
        this.size++
        return this
    }
    // 时间复杂度 O(1)
    unshift(val) {
        const node = new LinkNode(val)
        if (!this.head) {
            this.head = node
        } else {
            let temp = this.head
            this.head = node
            this.head.next = temp
        }
        this.size++
        return this
    }
    // 时间复杂度 O(1)
    shift() {
        if (!this.head) return -1
        this.head = this.head.next
        this.size--
        return this
    }
    // 时间复杂度 O(2n)
    pop() {
        return this.removeAtIndex(this.size-1)
    }
    // 时间复杂度 O(2n)
    removeAtIndex(index) {
        if (!this.head || index >= this.size || index < 0 || this.size == 0) return

        const prevNode = this.findNode(index-1)
        const nextNode = this.findNode(index+1)
        const currNode = this.findNode(index)
        // 正常情况
        if (prevNode && nextNode) {
            prevNode.next = nextNode
        }
        // 索引为 0, size 大于 1 === shift
        if (!prevNode && nextNode) {
            this.head = this.head.next
        }

        // 索引为 size-1 === pop
        if (prevNode && !nextNode) {
            prevNode.next = null
        }

        // 索引为 0，size为 1 
        if (!prevNode && !nextNode) {
            this.head = null
        }
        this.size--
        return currNode
    }

    // 时间复杂度 O(2n)
    addAtIndex(val, index=this.size) {
        const node = new LinkNode(val)
        if (!node && (index > this.size || index < 0)) return

        // 尾不追加
        if (this.size === 0 || index === this.size) return this.push(node)

        // 头部追加
        if (index === 0) return this.unshift(node)

        // 中间部位
        const prevNode = this.findNode(index-1)
        const nextNode = this.findNode(index+1)

        prevNode.next = node
        node.next = nextNode
        this.size++
        return this
    }

    // 清空单链表
    clear() {
        this.head = null
        this.size = 0
        return this
    }

    // 翻转链表
    reverse() {
        if (this.head === null || this.head.next === null) return this.head
        // ... 待更新
        return this
    }
}

var list = new LinkList()


list.push('a').push('b').push('c')

console.log(list)

[liuliudaren]

// 单向

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

class oneWayList{
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    addFirst = val => {
        let node = new Node(val);

        if(this.size==0) {
            this.first = this.last = node;
        } else {
            node.next = this.first;
            this.first = node;
        }
        this.size++;
    }
    addLast = val => {
        let node = new Node(val);

        if(this.size ==0 ) {
            this.first = this.last = node;
        } else{
            this.last.next = node;
            this.last = node;
        }
        this.size++;
    }
    add = (index, val ) =>{
        let node = new Node(val);
        let point = this.first;

        if(index ==0 ) return this.addFirst(val);
        if( index == this.size ) return this.addLast(val);
        if(index<0 || index>this.size) return;

        for(let i=1; i<index; i++) {
            point = point.next;
        }

        node.next = point.next;
        point.next = node;

        this.size++;
    }
    deleteFirst = () =>{
        if(this.size===0) return;
        if(this.size ===1) this.first = this.last = null;

        let first = this.first;
        this.first = this.first.next;
        first.next = null;

        this.size--;
    };
    deleteLast = () =>{
        let point = this.first;

        if(this.size===0) return;
        if(this.size ===1) this.first = this.last = null;


        for(var i =1; i<this.size-1;i++){
            point = point.next;
        }

        point.next = null;
        this.last = point;

        this.size--;

    }

    delete = index =>{
        let point = this.first;
        let deleteNode;

        if(this.size===0) return ;
        if(index === 0 ) return this.deleteFirst();
        if(index === this.size-1 ) return this.deleteLast();

        for(var i=1; i<index-1; i++ ) {
            point = point.next;
        }

        deleteNode = point.next;
        point.next = point.next.next;
        deleteNode.next = null;

        this.size--;
    }

    set = (index,val,type) =>{
        let point = this.first;
        if(this.size===0 || index<0 || index>this.size-1) return;

        for(var i=1; i<index; i++ ) {
            point = point.next;
        }

        if(type==='get') {
            return point.val;
        } else {
            point.val = val;
        }
    }
    get = index =>{
        return this.set(index,'','get');
    }
}

//////////////////////////////////////////////////////////////////////////////
// 双向
class Node{
constructor(val){
this.val = val;
this.prev=null;
this.next=null;
}
}

class twoWayList{
        constructor(){
            this.first=null;
            this.last = null;
            this.size =0;
    }
    addFirst = val =>{
        let node = new Node(val);
        if(this.size===0) {
            this.first = this.last = node;
        } else {
            node.next = this.first;
            this.fist.prev=node;
            this.first = node;
        }

        this.size++;
    }
    addLast = val => {
        let node = new Node(val);
        if(this.size===0) {
            this.first = this.last = node;
        } else {
            node.prev = this.last;
            this.last.next=node;
            this.last = node;
        }

        this.size++;
    }
    add=(index,val) =>{
        let node = new Node(val);
        let point = this.first;

        if(index===0) return this.addFirst(val);
        if(index===this.size) return thsi.addLast(val);
        if(index<0 || index>this.size) return;

        for(var i=1;i<index;i++) {
            point = point.next;
        }
        node.prev= point;
        node.next = point.next;
        point.next.prev = node;
        point.next = node;

        this.size++;
    }

    deleteFirst = ()=>{
        if(this.size===0) return;
        if(this.sieze===1) {
            this.first = this.last = null;
        } else {
            this.first = this.first.next;
            this.first.prev.next = null;
            this.first.prev = null;
        }

        this.sieze--;
    }

    deleteLast = () => {
        if(this.size===0) return;
        if(this.size===1) {
            this.first = this.last = null;
        } else {
            this.last = this.last.prev;
            this.last.next.prev = null;
            this.last.next = null;
        }

        this.sieze--;
    }
    delete = index => {
        let point = this.first;

        if(index===1) return this.deleteFirst();
        if(index === this.size) return this.deleteLast();
        if(index<=0 || index>this.size ) return;

        for(let i=1;i<index;i++) {
            point = point.next;
        }

        point.prev.next = point.next;
        point.next.prev = point.prev;
        point.prev = point.next = null;

        this.size--;
    }

    set = (index,val) => {
        let point = this.first;
        if(index<=0 || index>this.size) return;
        if(index===1) {
            return point.val=val;
        }

        for(var i=1;i<index;i++) {
            point= point.next;
        }
        point.val = val;

    }
    get = (index) =>{
        let point = this.first;
        if(index<=0 || index>this.size) return;
        if(index===1) {
            return point.val;
        }

        for(var i=1;i<index;i++) {
            point= point.next;
        }

        return point.val;
    }
}

复杂度O(n)

[YoungYang7]

class Node{
    constructor(data){
        this.data=data
        this.next=null
    }
}
class LinkedList{
    constructor(){
        this.head=null
        this.tail=null
    }
    push(data){
        const node=new Node(data)
        if(!this.head){
            this.head=node
            this.tail=node
        }
        this.tail.next=node
        this.tail=node
    }
    ...
}

参考这篇文章：https://mp.weixin.qq.com/s/my_lAFqYGTrr8smxNSlUqg

[shancw96]

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

class NodeList{
  constructor(array){
    array.forEach((val,index)=>{
      index == 0?this.head = new Node(val) : this.insertNewNode(val)
    })
  }
  insertNewNode(val){
    let cur = this.head ;
    while(cur.next){
      cur = cur.next
    }
    cur.next = new Node(val)
  }
  /**
   * ohter methods
   * ...
   * ...
   * ..
   *  */

}

[0425liu]

今天又流下了眼泪，单向链数据结构是啥我都不知道

[BranceLee]

详解

class LinkList {
  constructor() {
    this.head = null
  }

  find(value) {
    let curNode = this.head
    while (curNode.value !== value) {
      curNode = curNode.next
    }
    return curNode
  }

  findPrev(value) {
    let curNode = this.head
    while (curNode.next!==null && curNode.next.value !== value) {
      curNode = curNode.next
    }
    return curNode
  }

  insert(newValue, value) {
    const newNode = new Node(newValue)
    const curNode = this.find(value)
    newNode.next = curNode.next
    curNode.next = newNode
  }

  delete(value) {
    const preNode = this.findPrev(value)
    const curNode = preNode.next
    preNode.next = preNode.next.next
    return curNode
  }
}

class Node {
  constructor(value, next) {
    this.value = value
    this.next = null
  }
}

find 中，curnode.next =null 时，null.value 是会报错的---》

[maginapp]

链表没有随机访问的能力，获取第n个元素需要从第一个元素逐步查询
增删改查的时间复杂度是o(n)

const LinkList = (function () {
    class _Node {
        constructor(value) {
            this.value = value;
            this.next = null;
        }
    }
    class LinkList {
        constructor() {
            this.head = null;
        }
        find(val) {
            let node = this.head;
            while (node && node.value !== val) {
                node = node.next;
            }
            return node;
        }
        findPre(val) {
            let node = this.head;
            while (node) {
                if (node.next && node.next.value === val) {
                    break;
                }
                node = node.next;
            }
            return node;
        }
        delete(val) {
            let preNode = this.findPre(val);
            let curNode;
            if (preNode) {
                curNode = preNode.next;
                preNode.next = curNode.next;
            }
            else {
                curNode = this.find(val);
                if (curNode) {
                    this.head = curNode.next;
                }
            }
            return curNode;
        }
        unshift(val) {
            let node = new _Node(val);
            let first = this.head;
            if (!first)
                this.head = node;
            else {
                node.next = first;
                this.head = node;
            }
            return node;
        }
        push(val) {
            let node = new _Node(val);
            let curNode = this.head;
            while (curNode && curNode.next) {
                curNode = curNode.next;
            }
            !curNode ? this.head = node : curNode.next = node;
            return node;
        }
        insert(newValue, value) {
            let newNode = new _Node(newValue);
            let curNode = this.find(value);
            if (!curNode)
                this.unshift(newValue);
            else {
                newNode.next = curNode.next;
                curNode.next = newNode;
            }
            return newNode;
        }
    }
    return LinkList;
}());

[yaoocheng]

直接一个单链表给他甩脸上

[Lingdeqing]

// 单向链表
class ListNode{
    constructor(val, next=null){
        this.val = val
        this.next = next
    }
}
class List {
    #head = null;
    #size = 0;
    // 末尾追加节点
    appendNode(newNode){
        if(this.isEmpty()){
            this.#head = newNode
        } else {
            let tail = this.#head;
            while(tail.next){
                tail = tail.next
            }
            tail.next = newNode
        }
        this.#size ++
    }
    // 指定节点前面插入节点
    insertBefore(newNode, referenceNode){
        if(!referenceNode) return false
        if(this.isEmpty()) return false

        // 插入头节点前面
        if(referenceNode === this.#head){
            newNode.next = this.#head
            this.#head = newNode
            this.#size ++
            return
        }

        // 插入其他节点前面
        let prev = this._findPrevNode(referenceNode)
        if(!prev) return false
        prev.next = newNode
        newNode.next = referenceNode
        this.#size ++
        return true
    }
    // 删除指定节点
    removeNode(node){
        if(!node) return false
        if(this.isEmpty()) return false

        // 删除头节点
        if(node === this.#head){
            this.#head = node.next;
            node.next = null
            this.#size --
            return true
        }

        // 删除其他节点
        let prev = this._findPrevNode(node)
        if(!prev) return false
        prev.next = node.next
        node.next = null
        this.#size --
        return true
    }

    // 按值查找节点
    findNodeByVal(val){
        let node = this.#head
        while(node){
            if(node.val === val){
                return node
            }
            node = node.next
        }
        return null
    }
    // 查找节点前面的邻居
    _findPrevNode(node){
        if(this.isEmpty()) return null
        let prev = this.#head;
        while(prev.next!==node){
            prev = prev.next;
        }
        if(prev.next === node){
            return prev
        }
        return null
    }
    // 是否为空
    isEmpty(){
        return this.#head === null
    }
    // 获取链表长度
    size(){
        return this.#size
    }
}

[G-WangZH]

问这样的问题不知道是出于什么考虑的？