Topic describes

Given a linked list, delete the NTH last node of the list and return the first node of the list.

Example:

Given a linked list: 1->2->3->4->5, and n = 2.

When the penultimate node is deleted, the linked list becomes 1->2->3->5.

A given n is guaranteed to be valid.

Advanced:

Can you try using a scan implementation?

Source: LeetCode link: leetcode-cn.com/problems/re…

Their thinking

Reference: concise two-pointer diagram

Fast and slow double pointer:

  • Establish fast Pointers P and slow Pointers Q, and remember n as the initial value, i.e. the penultimate NTH number to be deleted.
  • The fast pointer P goes first, and the variable N decreases;
  • When n=0, the fast pointer P has taken n more steps than the slow pointer Q. For example, if n==-1, q= q.ext; P = p.n ext);
  • When the p pointer points to null, the loop body stops executing. At this point, the fast pointer P just takes n+1 more steps than the slow pointer Q;
  • Delete the next node that is the slow pointer. (i.e. Q.ext = q.ext.next)
  • Special case: when the head node needs to be deleted (that is, when the linked list has five nodes and the fifth from last node is deleted), the fast pointer P only takes n more steps than the slow pointer Q, and the slow pointer Q does not move, at this point, n==0,p==null; Return the next node of the head node; return head.next(q.next);

Definition of node class

/*** * Definition for singly-linked list. * Linked list node Definition; */ function ListNode(val){ this.val=val; this.next=null; }Copy the code

A:

  • Example parameters are [1,2,3,4,5] and 2.
  • @param:head is the index to the linked list header val==1;
  • @param:n is the penultimate node to be deleted;
  • Examples of special cases: [1] and 1; Or [1,2,3,4,5] and 5; The deleted node is the head node.

code

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; *} * /
/ * * *@param {ListNode} head
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {
// Create a fast pointer;
  let p=head,q=head;
  // p points to null as the termination condition;
 
  while(p){
      // The slow pointer starts to move
      if(n<0){
          q=q.next;
      }
      // The fast pointer moves n steps first
      n--;
      p=p.next;
  }//end of while 
   if(n==0) {return head.next;
  }
  q.next=q.next.next;
  return head;
};
Copy the code

Idea 2:

  • Establish fast Pointers and slow Pointers, and remember n as the initial value, i.e. the penultimate NTH number to be deleted.
  • For fast Pointers, step N-1 is performed first;
    • If fast. Next ==null, n==sz;
      • Return head.size directly
    • Otherwise, fast=fast.next, in which case the fast pointer takes n more steps than the slow pointer;
  • The fast and slow Pointers are executed simultaneously, and the termination condition is fast&&fast. Next;
    • That is fast fast pointer to the last node to stop;
    • Delete the node after the slow pointer slow.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
 * @param {number} n
 * @return {ListNode}* /
var removeNthFromEnd = function(head, n) {
   // Double pointer implementation
   let fast =head,slow=head;
    // Only n-1 steps have been taken
    while(--n){  
        fast=fast.next;
    }
     // Special cases have priority;
    // If the fast pointer is already the last one in the linked list, return head.next; I'm going to do the n= sz case ahead of time
    if(! fast.next){return head.next;
    }
    // The fast pointer takes n more steps than the slow pointer;
    fast=fast.next;
    
    // The fast and slow Pointers advance simultaneously
    while(fast&&fast.next){
        fast=fast.next;
        slow=slow.next;
    }
    slow.next=slow.next.next;
    return head;

};
Copy the code