707. 设计链表

707. 设计链表

/**
 * 双链表
 * 使用虚拟表头是为了简化对实际结点的操作，将所有操作会统一为在链表中间修改结点
 */
class MyLinkedList {
  head = new LinkNode(null); // 表头。虚拟表头
  tail = new LinkNode(null); // 表尾。虚拟表尾
  len = 0; // 链表的长度

  constructor() {
    // 将两个虚拟头尾相连，即默认的空链表
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  getNode(index: number): LinkNode {
    // 如果超过了链表长度
    // 因为 index 从 0 开始，所以是 >= len
    // 返回 -1
    if (index >= this.len) {
      return null;
    }

    // 获取 index 处的 node
    let currentNode = this.head;

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

    return currentNode;
  }

  get(index: number): number {
    const node = this.getNode(index)

    if (!node) {
      return -1;
    }

    return node.val;
  }

  addAtHead(val: number): void {
    const oldHead = this.head.next; // 旧的头结点

    this.insertBefore(oldHead, val);

  }

  addAtTail(val: number): void {
    const oldTail = this.tail; // 虚拟尾结点

    this.insertBefore(oldTail, val)
  }

  addAtIndex(index: number, val: number): void {
    // 如果大于链表长度
    // 不处理
    if (index > this.len) {
      return;
    }

    // 等于链表长度
    // 插入尾部
    if (index === this.len) {
      this.addAtTail(val);
    } else {
      const nextNode = this.getNode(index); // 旧的结点
      this.insertBefore(nextNode, val)
    }
  }

  deleteAtIndex(index: number): void {
    const oldNode = this.getNode(index); // 旧的结点

    // 如果能获取到结点说明有效，开始删除
    if (oldNode) {
      const prevNode = oldNode.prev
      const nextNode = oldNode.next

      // 将 oldNode 的指针置为 null
      oldNode.prev = null;
      oldNode.next = null;

      // 将 prevNode 和 nextNode 连起来
      prevNode.next = nextNode
      nextNode.prev = prevNode

      this.len -= 1
    }
  }

  /**
   * 在前面插入
   */
   insertBefore(nextNode: LinkNode, val: number) {
      const prevNode = nextNode.prev; // 上一个结点
      const newNode = new LinkNode(val); // 新插入的结点

      // 在旧的结点之前插入
      nextNode.prev = newNode;
      newNode.next = nextNode;

      // 调整上一个结点的指针
      prevNode.next = newNode;
      newNode.prev = prevNode;

      this.len += 1
   }
}

/**
 * 链表结点
 */
class LinkNode {
  val = null; // 当前结点
  next = null; //下一个结点
  prev = null; // 上一个结点

  constructor(val: number) {
    this.val = val;
  }
}

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