“This is the first day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

第23 日 2021.1.18

Delete the penultimate node of the linked list

• Leetcode: leetcode-cn.com/problems/re…
• Difficulty: Medium
• Method: double pointer, stack

The title

• Give you a linked list, delete the last of the linked listnAnd returns the head of the list.

The sample

• Example 1

Input: head = [1,2,3,4,5], n = 2Copy the code

• Example 2

Input: head = [1], n = 1 output: []Copy the code

• Example 3

Input: head = [1,2], n = 1Copy the code

prompt

• The number of nodes in the linked list is zerosz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Advanced: Can you try using a scan implementation?

solution

Solution 1: General practice

• Step 1: Iterate through the linked list, recording the total length of the listlen
• Step 2: Use the total lengthlenMinus thenI’m going to get the number of iterations from the front to the backm
  • m0: the number of nodes searched from the front to the back in the current linked list is 0, that is, the head node needs to be deleted
  • mNot 0: traversalmTo find the previous node of the node to be deleted
• Step 3: List delete node operation, will the current node of the previous nodenextPoints to the next node after the current node
  • That is:prev.next = prev.next.next

var removeNthFromEnd = function(head, n) { 
  let h = head; 
  // Record the length of the linked list
  let len = 0; 
  while (h) { 
    len++; 
    h = h.next; 
  } 
  // console.log(' list length ',len);
  len = len - n; / / 1 1
  // Delete the header len2 n2
  if (len == 0){ 
    head = head.next; 
    return head; 
  }
  // Delete the tail node
  // Delete the intermediate node
  h = head; 
  while (len > 1 && h) {
    // Iterate over the n-1 node
    len--; 
    h = h.next; 
  }
  h.next = h.next.next; 
  return head; 
};
Copy the code

Solution 2: write your own double pointer approach

• The first step:slowThe pointer points to the head of the list,fastPointers andslowThey all start at the head of the list.
• The second step:whilecyclefastExecute when the pointer is true (the third solution is optimized 🆕)
  • fastThe pointer traverses forwardnAfter a node, determinefastWhether the pointer is null (not a valid node), and if null, the node to be deleted isslowThe node, the head node, executesslow = slow.nextThe output can be
  • fast.nextIs empty,fastThe pointer has already found the last node in the list (a valid node), so the slow pointer points to the node before the node that needs to be removed. And then you break out of the loopbreak
  • fast && fast.nextIf both values are true, it indicates that the node to be deleted has not been foundslowMove the pointer forward one node,fastPointer toslowThe node to which the pointer points is traversed againnEach node is repeated ♻️ until the node to be deleted is found.
• Step 3: Because only one node is to be deleted, directly delete the previous node of the node to be deletednextPoint to the next node to be deleted.

/**
* 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) {
  let slow = head;
  let fast = slow;
  // Record the number of cycles required
  let nn = n;

  while (fast) {
    // Loop through it once
    while (nn > 0) {
      nn--;
      fast = fast.next;
    }
    // fast. Next finds the last node
    if(! fast) {// Is not a valid node
      slow = slow.next;
      return slow;
    }
    if(! fast.next)break;
    slow = slow.next;
    fast = slow;
    nn = n;
  }
  / / the connection
  // Delete only one
  slow.next = slow.next.next;
  return head;
};
Copy the code

Solution 3: (optimization) refer to leetcode’s official solution article after writing the double pointer approach

• Step 1: Create a new table headerslowPointer to the newly created table header
• Step 2: WillfastThe pointer points to the actual headerhead“And traverse backwardsnAt this timeslowandfastThe distance between the hands, exactlyn
• Step 3 :(⚠️ is also my double pointer when I did not consider the practice, do a lot of repeated traversal) here do not need to beslowPointer assignment tofastPointer, iterate againnA node; It was already determined in step twoslowwithfastThe distance between the Pointers is based on the moveslowThe next node is also going to befastMove one node back, always ensuring that the spacing between the two Pointers isnTwo nodes.
• Step 4: WhenfastPointer tonull.slowPoints to the previous node to be deletedslow.next = slow.next.next
• 🏷️ Summary: In this way, it is not necessary to determine whether the first node is deleted

/**
* 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) {
  // It can also be optimized
  // 1. After fast moves N for the first time, the distance between slow and fast is fixed
  // Then slow moves 1, fast moves 1
  // 2. Create a new table header
  
  // Create a new header pointer
  let dummy = new ListNode(0,head); 
  let slow = dummy;
  let fast = head;
  
  for (let i = 0; i < n; i++) {
    // Now move the fast pointer forward n steps
    fast = fast.next;
  }
  
  // The double pointer moves forward
  while (fast) {
    slow = slow.next;
    fast = fast.next;
  }
  slow.next = slow.next.next;
  // Return the real list head node
  return dummy.next;
};
Copy the code

The appendix

• Notes for linked lists ⚠️
  • Always check that the node is empty before calling the next field.
  • Getting the next node of an empty node causes a null pointer error. For example, before we run fast = fast.next-next, we need to check that fast and fast.next are not empty.
  • Carefully define the end condition of the loop.