19. 删除链表的倒数第 N 个结点（中等）

约定不等于承诺〃 2022-09-09 06:47 110阅读 0赞

Leetcode链接：[19. 删除链表的倒数第 N 个结点][19. _ N]

### 题目描述 ###

> 给你一个链表，删除链表的倒数第 `n` 个结点，并且返回链表的头结点。  
>   
>   
> 进阶：你能尝试使用一趟扫描实现吗？

示例 1：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_14_color_FFFFFF_t_70_g_se_x_16]

> 输入：head = \[1,2,3,4,5\], n = 2  
> 输出：\[1,2,3,5\]

示例 2：

> 输入：head = \[1\], n = 1  
> 输出：\[\]

示例 3：

> 输入：head = \[1,2\], n = 1  
> 输出：\[1\]

提示：

> 链表中结点的数目为 `sz`  
> `1 <= sz <= 30`  
> `0 <= Node.val <= 100`  
> `1 <= n <= sz`

### 源码 ###

/**
     * 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) {
        
            // 1. 添加头部
            ListNode newHead = new ListNode(-1);
            newHead.next = head;
            ListNode prev_left = newHead;
            ListNode left = head;
            // 2. 快慢指针
            ListNode right = head;
    
            // 3. right移动n步 因为right要移动为最后一个节点的后面，值为null
            for(int i = 0; i < n; i++){
        
                right = right.next;
            }
            // 4. 三个指针以相同的速度向前移动
            while(right != null){
        
                prev_left = prev_left.next;
                left = left.next;
                right = right.next;
            }
    
            prev_left.next = prev_left.next.next;
            return newHead.next;
        }
    }

[19. _ N]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5LqM6L-b5Yi25p2v6I6r5YGc_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/e0622c7e6a1d48f5a0cc49791a695851.png