[record of question brushing] 19. Delete the penultimate node of the linked list

One 、 Title Description

source ：

Power button （LeetCode）

I'll give you a list , Delete the last of the linked list  

n

 ** Nodes , And return the head node of the list .

Input ： head = [1,2,3,4,5], n = 2
Output ： [1,2,3,5]


Example  2：

Input ：head = [1], n = 1
Output ：[]


Example  3：

Input ：head = [1,2], n = 1
Output ：[1]


Tips ：

The number of nodes in the list is  sz

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz
  Advanced ：
    Can you try a scan implementation ？

II. Train of thought analysis

When deleting nodes , We need to know the length of the node to determine the penultimate n Location of nodes .

If you traverse once , Find once in , Can also do . The advanced requirement of the topic is to try a scan .

Then, if we realize it with one scan, we can realize it with the help of the concept similar to window

• Let's make this window a fixed length  
  n
    A window of ,

• The left side of the window is the starting point of the linked list .

• Then move the window , When the right side of the window moves to the end node of the linked list, it is empty , The left side of the window points to the one to be deleted   Last but not least
  n
  Nodes

As the sample  1

3、 ... and 、 Code implementation

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
 public ListNode removeNthFromEnd(ListNode head, int n) {
 ListNode dummy = new ListNode(0, head);
 ListNode R = head;
 ListNode L = dummy;
 for (int i = 0; i < n; ++i) {
 R = R.next;
 }
 while (R != null) {
 R = R.next;
 L = L.next;
 }
 L.next = L.next.next;
 ListNode res = dummy.next;
 return res;
 }
}


Complexity analysis

• Time complexity ：
  
  
  , among &nbsp;
  n
  &nbsp; It's the length of the list

• Spatial complexity ：
  
  

Running results

summary

This topic also uses

Double pointer  +  Windows are similar concepts （ Fixed length ）

, Use the length and movement of this window , To determine the penultimate

n

Location of nodes . To achieve one-time traversal .