707.设计链表.md

707.设计链表

/*
 * @lc app=leetcode.cn id=707 lang=typescript
 *
 * [707] 设计链表
 */

// @lc code=start

class MyLinkedList {
  constructor() {}

  get(index: number): number {}

  addAtHead(val: number): void {}

  addAtTail(val: number): void {}

  addAtIndex(index: number, val: number): void {}

  deleteAtIndex(index: number): void {}
}

/**
 * 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)
 */
// @lc code=end

解法 1: 数组模拟链表

class MyLinkedList {
  private nums: number[] = []
  constructor() {}

  get(index: number): number {
    return this.nums[index] ?? -1
  }

  addAtHead(val: number): void {
    this.nums.unshift(val)
  }

  addAtTail(val: number): void {
    this.nums.push(val)
  }

  addAtIndex(index: number, val: number): void {
    if (index < 0 || index > this.nums.length) return
    this.nums.splice(index, 0, val)
  }

  deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.nums.length) return
    this.nums.splice(index, 1)
  }
}

解法 2: 双链表

class NodeList {
  val: number = 0
  next: NodeList | null = null
  pre: NodeList | null = null
  constructor(val?: number) {
    if (val !== undefined) this.val = val
  }
  setNext(next: NodeList | null) {
    if (next) {
      if (this.next) next.next = this.next
      next.pre = this
    }
    if (this.next) this.next.pre = next
    this.next = next
  }
}
class MyLinkedList {
  private head: NodeList | null = null
  private tail: NodeList | null = null
  private lenght: number = 0
  constructor() {}

  get(index: number): number {
    if (index < 0 || index >= this.lenght) return -1
    let node = this.head
    while (index--) node = node!.next
    return node!.val
  }

  addAtHead(val: number): void {
    const node = new NodeList(val)
    node.setNext(this.head)
    this.head = node
    if (!this.tail) this.tail = node
    this.lenght++
  }

  addAtTail(val: number): void {
    const node = new NodeList(val)
    if (this.tail) {
      this.tail.setNext(node)
      this.tail = node
    } else {
      this.head = this.tail = node
    }
    this.lenght++
  }

  addAtIndex(index: number, val: number): void {
    if (index > this.lenght) return
    if (index <= 0) this.addAtHead(val)
    else if (index === this.lenght) this.addAtTail(val)
    else {
      let newNode = new NodeList(val)
      let node = this.head
      while (--index) node = node!.next
      node!.setNext(newNode)
      this.lenght++
    }
  }

  deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.lenght) return
    if (this.lenght === 1) {
      this.head = this.tail = null
    } else {
      if (index === 0) {
        const next = this.head!.next
        this.head!.setNext(null)
        this.head = next
      } else if (index === this.lenght - 1) {
        const pre = this.tail!.pre!
        pre.setNext(null)
        this.tail = pre
      } else {
        let node = this.head
        while (--index) node = node!.next
        const next = node!.next!.next
        node!.next = null
        node!.setNext(null)
        node!.setNext(next)
      }
    }
    this.lenght--
  }
}

test.each([
  {
    input: {
      ops: [
        'MyLinkedList',
        'addAtHead',
        'addAtIndex',
        'get',
        'addAtHead',
        'addAtTail',
        'get',
        'addAtTail',
        'get',
        'addAtHead',
        'get',
        'addAtHead',
      ],
      params: [[], [5], [1, 2], [1], [6], [2], [3], [1], [5], [2], [2], [6]],
    },
    output: [null, null, null, 2, null, null, 2, null, -1, null, 5, null],
  },
  {
    input: {
      ops: ['MyLinkedList', 'addAtHead', 'addAtTail', 'addAtIndex', 'get', 'deleteAtIndex', 'get'],
      params: [[], [1], [3], [1, 2], [1], [1], [1]],
    },
    output: [null, null, null, null, 2, null, 3],
  },
  {
    input: {
      ops: [
        'MyLinkedList',
        'addAtHead',
        'addAtHead',
        'addAtHead',
        'addAtIndex',
        'deleteAtIndex',
        'addAtHead',
        'addAtTail',
        'get',
        'addAtHead',
        'addAtIndex',
        'addAtHead',
      ],
      params: [[], [7], [2], [1], [3, 0], [2], [6], [4], [4], [4], [5, 0], [6]],
    },
    output: [null, null, null, null, null, null, null, null, 4, null, null, null],
  },
])('input: param', ({ input: { ops, params }, output }) => {
  const cls = new MyLinkedList()
  const res: (null | number)[] = [null]
  for (let i = 1; i < ops.length; i++) {
    res.push(cls[ops[i]](...params[i]) ?? null)
  }
  expect(res).toEqual(output)
})