[Meng Xin problem solving] Delete the Nth node from the bottom of the linked list

关于我：微信公众号：面试官问,原创高质量面试题,始于面试题,但不止于面试题.【萌新解题】系列文章试图从新人的角度去看待和解决力扣题目,本题是力扣第 19 题 删除链表的倒数第 N 个结点：https://leetcode.cn/problems/remove-nth-node-from-end-of-list.

题目描述

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点.

前置知识点

Many linked list related questions can be used双指针法来解决.The double pointer method can be subdivided into two different methods according to the different movement modes of the two pointers：

• 前后双指针：That is, a pointer moves several steps in advance toward the pointer to the next node in the linked list,Then move the second pointer at the same time
• 快慢双指针：That is, the two pointers move at different speeds in the linked list,Usually the fast pointer moves two steps at a time towards the pointer to the next node,慢的指针一次只移动一步.

解题说明

This question is a typical application of front and rear double pointers,通常为了删除一个节点,应该找到被删除节点的前一个节点,然后把该节点的 next 指针指向它下一个节点的下一个节点,这样下一个节点没有被其他节点引用,也就相当于被删除了. To delete the penultimate of the linked list n 个节点,Removes the properties of a node according to the linked list,We didn't directly find the node to delete,Instead, find the penultimate n+1 个节点,Then by modifying the penultimate n+1 A pointer to a node implements deleting the penultimate n 个节点.

代码如下所示：

class Solution {
    /**
     * 通常为了删除一个节点,应该找到被删除节点的前一个节点,然后把该节点的next指针指向它下一个节点的下一个节点,这样下一个节点没有被其他节点引用,也就相当于被删除了. 
     * To delete the penultimate of the linked list n 个节点,Removes the properties of a node according to the linked list,We didn't directly find the node to delete
     * Instead, find the penultimate n+1 个节点,Then by modifying the penultimate n+1 A pointer to a node implements deleting the penultimate n 个节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Introduce sentinel nodes,Avoid handling e.g. empty linked lists of inputs,Or the deleted node is a boundary problem such as the head node of the original linked list
        ListNode dummy = new ListNode();
        dummy.next = head;

        // 前指针
        ListNode first = head;

        // 后指针
        ListNode second = dummy;

        // The front pointer moves to first n-1 的位置
        for (int i=0; i<n; ++i) {
            first = first.next;
        }

        // The front and rear double pointers move at the same time,until the previous pointer reaches the end of the linked list
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // At this point, the pointer has already pointed to the penultimate n+1 个节点,Delete its next node which is the penultimate one n 个节点即可
        second.next = second.next.next;

        return dummy.next;        
    }
}

复杂度分析

• 时间复杂度：O(n),其中 n 是链表的长度
• 空间复杂度：O(1),没有使用额外的存储空间