双向链表，求解《设计链表》

例题

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 库。

答案

双向链表

class Node {
  constructor(val = null, next = null, prev = null) {
    this.val = val
    this.next = next
    this.prev = prev
  }
}
var MyLinkedList = function() {
  this.tail = this.head = null
  this.size = 0
};

MyLinkedList.prototype.get = function(index) {
  const p = this.findAtIndex(index)
  return p ? p.val : -1
};

MyLinkedList.prototype.addAtHead = function(val) {
  if (this.head === null) this.head = this.tail = new Node(val)
  else this.head = this.head.prev = new Node(val, this.head)
  this.size++
};

MyLinkedList.prototype.addAtTail = function(val) {
  if (this.head === null) this.head = this.tail = new Node(val)
  else this.tail = this.tail.next = new Node(val, null, this.tail)
  this.size++
};

MyLinkedList.prototype.addAtIndex = function(index, val) {
  if (index > this.size) return
  if (index <= 0) return this.addAtHead(val)
  if (index === this.size) return this.addAtTail(val)
  const p = this.findAtIndex(index)
  p.prev = p.prev.next = new Node(val, p, p.prev)
  this.size++
};

MyLinkedList.prototype.deleteAtIndex = function(index) {
  if (index >= this.size || index < 0) return
  if (index === 0) {
    if (this.head.next !== null) this.head.next.prev = null
    this.head = this.head.next
  } else {
    const p = this.findAtIndex(index)
    p.prev.next = p.next
    if (p.next !== null) p.next.prev = p.prev
    if (index === this.size - 1) this.tail = p.prev
  }
  this.size--
};

MyLinkedList.prototype.findAtIndex = function(index) {
  if (index === 0) return this.head
  if (index >= this.size || index < 0) return null
  let i = 0
  if (index <= this.size >> 1) {
    let p = this.head
    while (p) {
      p= p.next
      if (++i === index) return p
    }
  } else {
    let p = this.tail
    while (p) {
      if (this.size - ++i === index) return p
      p = p.prev
    }
  }
}