Sword finger offer II 021 Delete the penultimate node of the linked list

Summary

Double pointer to the right , The right pointer goes to the end , Handle the penultimate with the left pointer n Nodes

subject

Given a linked list , Delete the last of the linked list n Nodes , And return the head node of the list .

link ：https://leetcode.cn/problems/SLwz0R/

Ideas

Finally, I entered the linked list stage .

Because it's a linked list , So we don't know the length of the linked list . This is a classic question , If it is toutie, go to the penultimate n Nodes , Then go through it first to get the length , Then traverse again or go back .

Of course , Here we still need to sacrifice our double pointer method . Starting from the chain header node , The right hand goes first , Walked a distance n after , The left pointer and the right pointer start at the same time . When the right pointer comes to the end , The next position of the left pointer is the penultimate position n Nodes .

in addition , The problem of linked list , A sentinel node is often used to point to the linked list head, It greatly facilitates our processing .

solution ： The sentinel node + Double pointer

Code

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode();
    //  The sentinel node can be used to easily handle the removed nodes head The situation of 
    dummy.next = head;
    ListNode left = dummy;
    ListNode right = dummy;
    int count = 0;
    //  Right pointer walking n Step 
    while (right.next != null && count < n) {
        right = right.next;
        count++;
    }
    //  Move left and right at the same time 
    while (right.next != null) {
        right = right.next;
        left = left.next;
    }
    //  Remove node 
    left.next = left.next.next;
    return dummy.next;
}