算法训练营第3天｜203.移除链表元素、707.设计链表、206.反转链表

var removeElements = function(head, val) {
  // 创建一个虚拟的头节点，使其统一循环的方式
  const newList = new ListNode(0, head)
  // 定义一个指针来遍历链表，但它只是个引用
  // 注意：
  // 用户可能认为cur是一个独立的副本，修改它不会影响原链表。
  // 但实际上，对象（包括链表节点）是通过引用传递的。
  // cur变量存储的是对链表节点的引用，而不是副本。
  let cur = newList
  // 只需要循环cur.next，就能循环原有的链表，因为cur.next 就等于 原有的链表head
  while(cur.next) {
    // 判断相等就改变指针
    if (cur.next.val === val) {
      // 将当前节点的 next 指向下个节点的 next，就能把当前下个节点删除
      cur.next = cur.next.next
    } else {
      // 否则将指针指向链表的下个节点
      // 因此，cur = cur.next只是将cur变量指向下一个节点，而不会改变原链表的结构。
      // 但如果是cur.next = newNext，则会直接修改链表节点之间的连接关系，从而改变原链表
      cur = cur.next
    }
  }
  return newList.next
};

class LinkNode {
  constructor(val, next) {
    this.val = val
    this.next = next
  }

}

var MyLinkedList = function() {
  this._size = 0
  this._head = null
  this._tail = null

};

MyLinkedList.prototype.getNode = function(index) {
  // 注意边界清理
  if (index < 0 || index >= this._size) return null
  let node = new LinkNode(0, this._head)
  // 使用指针来遍历链表
  while (index >= 0) {
    index --
    node = node.next
  }
  return node


};

/**
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
  if (index < 0 || index >= this._size) return -1
  return this.getNode(index).val
};

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
  let node = new LinkNode(val, this._head)
  this._size ++
  this._head = node
  // 每次的新增操作都需要考虑 size、head、tail 三个赋值的情况
  // 有头就一定有尾，所以在赋值的时候如果发现 tail 为空，就得赋值
  if (!this._tail) {
    this._tail = node
  }
};

/**
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
  let node = new LinkNode(val, null)
  // 这里要先++
  this._size ++
  if (this._tail) {
    // 如果添加的时候有尾节点，就得把已存在的尾节点的 next 指向新添加的
    this._tail.next = node
    this._tail = node
    return
  }
  // 如果没有尾节点，说明头尾节点都不存在
  this._tail = node
  this._head = node
};

/**
 * @param {number} index
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
  if (index > this._size) return;
  // 边界条件，可以复用上面的函数
  if (index <= 0) {
    this.addAtHead(val)
    return
  }
  if (index === this._size) {
    this.addAtTail(val)
    return;
  }
  // 需要找到上一个节点，然后对其进行插入新的节点
  let pre = this.getNode(index-1)
  pre.next = new LinkNode(val, pre.next)
  // 别忘了++
  this._size ++
};

/**
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
  if (index < 0 || index >= this._size) return
  // 判断边界，如果就是删除的首节点
  if (index === 0) {
    // 则需要把首节点的 next 赋值给首节点
    this._head = this._head.next
    // 还需要额外判断是否链表就只有一个节点的情况
    if (index === this._size -1) {
      this._tail = this._head
    }
    this._size --
    return;
  }
  // 没有边界情况就通用处理，删除指定位置的节点
  let pre = this.getNode(index-1)
  pre.next = pre.next.next
  if (index === this._size -1) {
    this._tail = pre
  }
  this._size --
};

//  双指针写法
var reverseList = function(head) {
  let temp = null, pre = null, cur = head
  while(cur) {
    temp = cur.next
    // 改变引用，会改变原链表
    cur.next = pre
    // 移动指针
    pre = cur
    cur = temp
  }
  // 当 cur = null时， 循环终止，此时 pre 就处在新的链表的头节点
  return pre
}

// 递归法
var reverseList = function(head) {
  // 定义递归函数
  function reverse(cur, pre) {
    // 当 cur = null时， 循环终止，此时 pre 就处在新的链表的头节点，递归结束的条件
    if(cur === null) return pre
    // 翻转节点指针
    const temp = cur.next
    cur.next = pre
    // 递归函数就不需要变更指针，只需要向下个循环函数参数中赋值新的 cur 和 pre 即可
    // 下一个 cur 就是 temp，pre 就是 cur
    return reverse(temp, cur)
  }

  return reverse(head, null)
}