链表

https://github.com/sisterAn/JavaScript-Algorithms/issues/12 > https://github.com/Juns-g/leetcode-answers/tree/main/notes

常见链表：单链表、双向链表、循环链表

链表不需要连续的内存空间，而是由一组零散的内存块，通过指针链接而成，所以每一个块中都需要包含当前节点的内容以及后继指针。

链表的插入和删除操作比较高效，时间复杂度为 O(1)，但是查找操作比较低效，时间复杂度为 O(n)。

学习链表的要点就是多画图多练习，一个通用做题步骤如下

1. 确定数据结构：单/双/循环
2. 确定思路
3. 画图实现：画图可以帮助我们发现思维中的漏洞
4. 边界条件
5. 代码实现

实现链表

707. 设计链表

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

class ListNode {
  val: number | null
  next: ListNode | null
  constructor(val: number | null = null, next: ListNode | null = null) {
    this.val = val === undefined ? 0 : val
    this.next = next === undefined ? null : next
  }
}

// #region
class MyLinkedList {
  head: ListNode | null
  size: number

  constructor() {
    this.head = null
    this.size = 0
  }

  getNode(index: number): ListNode | null {
    if (index < 0 || index >= this.size) return null
    let node = this.head
    for (let i = 0; i < index; i++) {
      node = node!.next
    }
    return node
  }

  get(index: number): number {
    if (index < 0 || index >= this.size) return -1
    return this.getNode(index)!.val as number
  }

  addAtHead(val: number): void {
    const oldHead = this.head
    this.head = new ListNode(val, oldHead)
    this.size++
  }

  addAtTail(val: number): void {
    if (this.size === 0) {
      this.size++
      this.head = new ListNode(val, null)
      return
    }
    const preNode = this.getNode(this.size - 1)
    preNode!.next = new ListNode(val, null)
    this.size++
  }

  addAtIndex(index: number, val: number): void {
    if (index < 0 || index > this.size) return
    if (index === 0) {
      this.addAtHead(val)
      return
    }
    if (index === this.size || this.size === 0) {
      this.addAtTail(val)
      return
    }
    const preNode = this.getNode(index - 1)
    const node = preNode!.next
    preNode!.next = new ListNode(val, node)
    this.size++
  }

  deleteAtIndex(index: number): void {
    if (index < 0 || this.size === 0) return
    if (index === 0) {
      this.head = this.head!.next
      this.size--
      return
    }
    const preNode = this.getNode(index - 1)
    if (!preNode || !preNode.next) return
    preNode.next = preNode.next.next
    this.size--
  }
}

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

// #endregion

const obj = new MyLinkedList()
obj.addAtHead(1)
obj.addAtTail(3)
console.log('🚀 ~ obj:', obj)
obj.addAtIndex(3, 2)
console.log('🚀 ~ obj:', obj)