Leetcode daily [2022 - 02 - 18]

Delete the node in the linked list

• Directly modify the value and the next node

  /**
   * 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;
  };

Delete the last of the linked list N Nodes

• Record length + Two traversal

  /**
   * 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++;
    }
  };

• Virtual header node + Speed pointer

  /**
   * 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);
      //  Defining the   Slow pointer   and   Quick pointer 
      //  Slow pointer   Points to the element and the number of elements on the left  +  Quick pointer   Points to the element and the number of elements on the right  =  Chain length 
      let slow = dummyHead;
      let fast = dummyHead;
  
      //  Move the fast pointer  n  position 
      for(let i = 0; i < n; i++) {
          fast = fast.next;
      }
  
      //  take   Quick pointer   Move   Chain length  - n  position 
      //  here   The slow pointer points to the penultimate  n + 1  position 
      while(fast && fast.next) {
          fast = fast.next;
          slow = slow.next;
      }
  
      //  Delete the last  n  position 
      slow.next = slow.next.next;
  
      return dummyHead.next;
  };

Reverse a linked list

• Double pointer

  /**
   * 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) {
      //  Temporary storage node 
      const node = resultHead;
      resultHead = currentOfHead;
      //  Because at this time  resultHead  And  currentOfHead  It points to the same node ,  So we need to change  currentOfHead  Point to 
      currentOfHead = currentOfHead.next;
      resultHead.next = node;
    }
  
    return resultHead;
  };

• recursive

  /**
   * 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;
  };

Summary

• There are two ways to delete a node in a linked list :

  • take The target node Of Last node Of Next node Point to The target node Of Next node , Such as pre.next = cur.next
  • Directly modifying Current node Of value by Current node Of Next node Value , modify Current node Next node by Current node Of Next node Of Next node , Such as cur.val = cur.next.val; cur.next = cur.next.next

• Delete the last N There are two ways for a node :

  • Record the length and traverse
  • Use double pointer , Using the relationship between two pointers

• There are two ways to reverse the linked list :

  • Insert node before
  • recursive