关于javascript:LeetCode-每日-2022-02-18

删除链表中的结点

• 间接批改值和下一个节点

  /**
   * Definition for singly-linked list.
   * function ListNode(val) {
   *     this.val = val;
   *     this.next = null;
   * }
   */
  /**
   * @param {ListNode} node
   * @return {void} Do not return anything, modify node in-place instead.
   */
  var deleteNode = function(node) {
      node.val = node.next.val;
      node.next = node.next.next;
  };

删除链表的倒数第 N 个结点

• 记录长度 + 两次遍历

  /**
   * Definition for singly-linked list.
   * function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
  /**
   * @param {ListNode} head
   * @param {number} n
   * @return {ListNode}
   */
  var removeNthFromEnd = function(head, n) {const dummyHead = new ListNode(0, head);
    let current = dummyHead;
    let length = 0;
    let index = 0;
  
    while(current.next) {
      length++;
      current = current.next;
    }
  
    current = dummyHead;
  
    while(length && current.next) {if(length - index === n) {
        current.next = current.next.next;
        return dummyHead.next;
      }
  
      current = current.next;
      index++;
    }
  };

• 虚构头节点 + 快慢指针

  /**
   * Definition for singly-linked list.
   * function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
  /**
   * @param {ListNode} head
   * @param {number} n
   * @return {ListNode}
   */
  var removeNthFromEnd = function(head, n) {const dummyHead = new ListNode(0, head);
      // 别离定义 慢指针 和 快指针
      // 慢指针 指向元素以及左侧元素个数 + 快指针 指向元素以及右侧元素个数 = 链表长度
      let slow = dummyHead;
      let fast = dummyHead;
  
      // 将快指针挪动 n 位
      for(let i = 0; i < n; i++) {fast = fast.next;}
  
      // 将 快指针 挪动 链表长度 - n 位
      // 此时 慢指针指向倒数第 n + 1 位
      while(fast && fast.next) {
          fast = fast.next;
          slow = slow.next;
      }
  
      // 删除倒数第 n 位
      slow.next = slow.next.next;
  
      return dummyHead.next;
  };

反转链表

• 双指针

  /**
   * Definition for singly-linked list.
   * function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
  /**
   * @param {ListNode} head
   * @return {ListNode}
   */
  var reverseList = function(head) {
    let resultHead = null;
    let currentOfHead = head;
  
    while(currentOfHead) {
      // 长期存储节点
      const node = resultHead;
      resultHead = currentOfHead;
      // 因为此时 resultHead 与 currentOfHead 指向的是同一节点, 因而需先扭转 currentOfHead 指向
      currentOfHead = currentOfHead.next;
      resultHead.next = node;
    }
  
    return resultHead;
  };

• 递归

  /**
   * Definition for singly-linked list.
   * function ListNode(val, next) {*     this.val = (val===undefined ? 0 : val)
   *     this.next = (next===undefined ? null : next)
   * }
   */
  /**
   * @param {ListNode} head
   * @return {ListNode}
   */
  var reverseList = function(head) {if(!(head && head.next)) return head;
  
      let newHead = reverseList(head.next);
      head.next.next = head;
      head.next = null;
  
      return newHead;
  };

小结

• 删除链表中的节点有两种形式:

  • 将 指标节点 的 上一节点 的 下一节点 指向 指标节点 的 下一节点, 如 pre.next = cur.next
  • 间接批改 以后节点 的 值 为 以后节点 的 下一节点 的值, 批改 以后节点的 下一节点 为 以后节点 的 下一节点 的 下一节点, 如 cur.val = cur.next.val; cur.next = cur.next.next

• 删除倒数第 N 个节点有两种形式:

  • 记录长度并遍历
  • 应用双指针, 利用两指针之间的关系

• 反转链表的两种形式:

  • 前插入节点
  • 递归