Linked list: delete the penultimate node of the linked list

subject

https://leetcode-cn.com/problems/SLwz0R/
Define a linked list , Please delete the penultimate in the linked list N Nodes , Output a new linked list .
Input list 1->2->3->4->5 , n = 2
Output ：1->2->3->5

What is a linked list

A list of nodes connected by pointers .
The time complexity of finding a node is O（N）
newly added 、 The time complexity of deleting a node is O（1）

Their thinking

Violence enumeration

We can traverse the linked list twice , Complete deletion of section n Tasks of nodes . The first traversal obtains the length of the linked list n, The second traversal will traverse to the reciprocal n+1 Stop when , Then count down n+1 The node of is modified to point to the reciprocal n-1 The node of .

Double pointer

The title requires us to traverse the linked list once and delete the n Nodes , So we have to find other ways .
We define a sentinel node and two pointers , The sentinel node is used to avoid the situation that the node is empty .
The two pointers are one before and one after . Divide into 3 Step ：
First step , Move the front pointer first n Step .
The second step , Move the front pointer and the back pointer at the same time , Until the previous pointer points to null , Stop moving .
The third step , The next node of the modified pointer points to , Delete node . Because the pointer just points to the reciprocal n+1 Nodes .

Code

/** * 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 dummyNode = new ListNode(0);
        dummyNode.next  = head;
        ListNode frontNode = head;
        ListNode backNode = dummyNode;

        for(int i = 0; i < n; ++i) {
    
            frontNode = frontNode.next;
        }
        while(frontNode != null) {
    
            frontNode = frontNode.next;
            backNode = backNode.next;
        }
        backNode.next = backNode.next.next;
        return dummyNode.next;

    }
}

summary

This question is used to examine the linked list , We define a sentinel node to optimize the deletion of head nodes . Two fast and slow pointers are defined to retrieve the deleted node .