LC19.删除链表的倒数第N个节点

题目地址(19. 删除链表的倒数第 N 个结点  labuladong 题解)

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

题目描述

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

进阶：你能尝试使用一趟扫描实现吗？

 

示例 1：


输入：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

前置知识

• 双指针 快慢指针

公司

• facebook 微软

思路

思路来源
这道题使用的是双指针中的快慢指针，采用快慢指针中的主要想法为求中点的部分，利用快慢指针步伐不一致的特点求解答案。
此题类似于求终点，但是更具有技巧性，三种递进式思考如下：

• 单纯的求中点问题，将快指针的步长设为2，慢指针的步长设为1，当快指针到达尾部时，慢指针到达的位置正好为中间位置（偶数在左）。
• 由于此题使用的是带头结点的单链表，不能直接 得出链表的长度n，而需要遍历一遍链表算出n的值，然后再遍历链表计算第n-k个节点，也就是说，这个解法需要遍历两次链表才能得到出倒数第k个节点。
• 但是根据题目要求，只遍历一次链表，所以不能通过确定链表长度来求解，可以通过下面的思路求解：
  快指针先走k步，快指针（fast）到达指定位置时，此时fast距离最后位置还有n-k步，此时，慢指针slow从head开始与fast以相同的步长前进，当fast到达最后位置时，slow到达的位置就是题目要求的倒数第k个元素的位置。
• 有了上面的思路，这题还是需要注意一些特殊点，1.不要直接走到倒数第k个元素，如果到达这里，没法进行元素的删除，所以走到倒数第k+1的位置即可。2.创建dummy虚拟节点，原因：为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进行正确的删除。

  关键点

• 双指针 快慢指针

代码

• 语言支持：Java

Java
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) {
        if(head.next==null) {
            head=null;
            return head;
        }
        //虚拟头结点

        ListNode dummy=new ListNode(-1);
        dummy.next=head;
        //要删除倒数第n个，要先找到第n+1个节点
        ListNode slow=dummy;
        ListNode fast=dummy;
        for(int i=1;i<=n+1;i++){
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;//slow表明了是指定元素
        }

        // ListNode tmp=slow;
        slow.next=slow.next.next;
        return dummy.next;
    }
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$