LeetCode-707.设计链表

题目详解

相关链接

• 代码随想录

思路

1. 先定义节点类ListNode，在他基础上实现链表类MyLinkedList
2. MyLinkedList的构造函数中需要链表的头结点head和长度size，后续的方法操作会更新相应的值

看完代码随想录之后的想法

• 链表的增删操作都可以直接用虚拟头节点

实现过程中遇到的困难

边界情况总是忘记处理，出现空指针异常，提交了多次才ac，比如：

• addAtTail时如果链表为空，实际就是addAtHead
• addAtIndex`index <= 0时实际就是addAtHead，index === this.size时实际就是addAtTail`
• deleteAtIndex可能会删头结点，需要用一个dummyHead来处理

代码

TypeScript

class LinkNode {
  val: any
  next: LinkNode | null
  constructor(val?: any, next?: LinkNode | null) {
    this.val = val
    this.next = next || null
  }
}

/**
* 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)
*/
class MyLinkedList {
  size: number
  head: LinkNode | null
  constructor() {
    this.size = 0
    this.head = null
  }

  get(index: number): number {
    let cur = this.head
    while (cur && index--) cur = cur.next
    return cur ? cur.val : -1
  }

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

  addAtTail(val: number): void {
    if (this.size === 0) {
      this.addAtHead(val)
      return
    }
    let cur = this.head
    while (cur.next) cur = cur.next
    cur.next = new LinkNode(val)
    this.size++
  }

  addAtIndex(index: number, val: number): void {
    if (index > this.size) return
    if (index <= 0) {
      this.addAtHead(val)
      return
    }
    if (index === this.size) {
      this.addAtTail(val)
      return
    }
    let cur = this.head
    while (index-- > 1) cur = cur.next
    cur.next = new LinkNode(val, cur.next)
    this.size++
  }

  deleteAtIndex(index: number): void {
    if (index < 0 || index >= this.size) return
    let dummyHead = new LinkNode()
    dummyHead.next = this.head
    let cur = dummyHead
    while (index--) cur = cur.next
    cur.next = cur.next.next
    this.head = dummyHead.next
    this.size--
  }
}

收获

• 对链表操作和手写数据结构有了更多认识