设计链表

https://leetcode.cn/problems/design-linked-list/description/

单链表

对链表的操作有两种方式：https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html#%E6%80%9D%E8%B7%AF

• 直接使用原来的链表进行操作
• 设置一个虚拟头结点进行操作

按照索引添加和删除结点要注意遍历得到关键结点应该是index前面的结点
根据索引get对应元素时，遍历得到的关键结点应该是index这个结点

var MyLinkedList = function () {
  this.val = null
  this.next = null
}

/**
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function (index) {
  let cur = this
  for (let i = 0; i <= index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return -1
    }
  }
  return cur.val
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  newNode.next = this.next
  // 从这一行可以清楚的看出，这是添加虚拟节点的操作方式
  this.next = newNode
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  newNode.next = null
  let cur = this
  while (cur.next) {
    cur = cur.next
  }
  cur.next = newNode
}

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  let cur = this
  for (let i = 0; i < index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return
    }
  }
  newNode.next = cur.next
  cur.next = newNode
}

/**
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
  let cur = this
  for (let i = 0; i < index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return
    }
  }
  if (!cur.next) return
  cur.next = cur.next.next
}

/**
 * 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)
 */

双链表

双链表多了一个prev要处理

var MyLinkedList = function () {
  this.prev = null
  this.val = null
  this.next = null
}


MyLinkedList.prototype.get = function (index) {
  let cur = this
  for (let i = 0; i <= index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return -1
    }
  }
  return cur.val
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function (val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  newNode.next = this.next
  newNode.prev = this
  this.next = newNode
}

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function (val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  newNode.next = null
  let cur = this
  while (cur.next) {
    cur = cur.next
  }
  newNode.prev = cur
  cur.next = newNode
}

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function (index, val) {
  const newNode = new MyLinkedList()
  newNode.val = val
  let cur = this
  for (let i = 0; i < index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return
    }
  }
  newNode.next = cur.next
  newNode.prev = cur
  cur.next = newNode
}

/**
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function (index) {
  let cur = this
  for (let i = 0; i < index; i++) {
    if (cur.next) {
      cur = cur.next
    } else {
      return
    }
  }
  if (!cur.next) return
  cur.next.prev = cur
  cur.next = cur.next.next
}

/**
 * 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)
 */