Delete the penultimate NTH node of the linked list

Topic link

Leetcode-cn.com/problems/re…

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 list becomes 1->2->3->5.Copy the code

Description:

A given n is guaranteed to be valid.

Advanced:

Can you try using a scan implementation?

The problem solving scheme

Train of thought

Tags: linked lists
The whole idea is to let the preceding pointer move firstnStep, after which the front and back Pointers move together until the front pointer reaches the tail
First set up pre pointer, pre pointer is a trick explained in question 2
Preset pointerpreThe next node points tohead, set the front pointer tostart, the last pointer isendBoth of them are equal topre
startI’m going to take n steps forward
afterstartandendMoving forward together, the distance between the two is zeronwhenstartWhen I get to the tail,endIs exactly the penultimate positionnA node
Because the node is to be deleted, it can only be deleted by moving to the previous node, so the end of the loop condition isstart.next ! = null
Return after deletionpre.nextWhy not just returnhead?headIt could be a deleted point
Time complexity: O(n)

code

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {    
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode start = pre, end = pre;
        while(n ! =0) {
            start = start.next;
            n--;
        }
        while(start.next ! =null) {
            start = start.next;
            end = end.next;
        }
        end.next = end.next.next;
        returnpre.next; }}Copy the code