JS实现LinkedList时prepend函数不符合预期，求提示与修复方案

问题排查提示 #

• 先审视链表的初始化逻辑：构造函数里head和tail都指向值为-1的节点，思考这个节点的定位——它是哨兵节点吗？你的prepend逻辑有没有考虑它的存在？
• 第一次执行prepend(1)时，this.head.nextNode的值是什么？此时你把新节点设为head，原来的head（值-1的节点）是否被正确保留在链表中？
• 第二次执行prepend(2)时，你只让新节点指向原head的nextNode，但原head（值1的节点）并没有被链接到新节点之后，这是不是导致节点丢失的原因？

修复方案 #

方案1：保留初始哨兵节点的情况 #

问题根源在于prepend逻辑错误地跳过了当前head节点，直接指向其nextNode，导致每次添加的新节点都无法链接到之前的有效节点。调整逻辑，让新节点的nextNode指向当前的head，再更新head为新节点：

class LinkedList {
  constructor() {
    this.head = new Node(-1);
    this.tail = this.head;
  };
  prepend(value) {
    // 新节点的next指向当前head
    const newNode = new Node(value, this.head);
    // 更新head为新节点
    this.head = newNode;
  };
};

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

执行prepend(1)再prepend(2)后，链表结构为：

LinkedList = {
  head: {
    nextNode: {
      nextNode: {
        nextNode: null,
        value: -1
      },
      value: 1
    },
    value: 2
  },
  tail: {
    nextNode: null,
    value: -1
  }
};

方案2：移除初始哨兵节点（更贴合常规链表实现） #

如果不需要哨兵节点，可将head和tail初始化为null，同时处理链表为空的边界情况：

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  };
  prepend(value) {
    const newNode = new Node(value);
    if (!this.head) {
      // 链表为空时，head和tail都指向新节点
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 链表非空时，新节点next指向当前head，更新head
      newNode.nextNode = this.head;
      this.head = newNode;
    }
  };
};

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

执行prepend(1)再prepend(2)后，得到你期望的结构：

LinkedList = {
  head: {
    nextNode: {
      nextNode: null,
      value: 1
    },
    value: 2
  },
  tail: {
    nextNode: null,
    value: 1
  }
};

内容的提问来源于stack exchange，提问作者mehkij