• 时间：2022-05-17
• 题目序号：19
• 难度：中等

问题描述

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

来源：力扣（LeetCode）

示例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

解题思路

题解部分参考自代码随想录。如有侵权，请联系进行删除~~

• 本题最先能想到的就是双重遍历（取长度，算位置，删元素）
• 除了双循环法，还可以使用双指针进行解题
• 还是使用虚拟头结点的方式来实现这两种方法（有虚拟头结点可以将首结点由特殊变为一般位置）

双重遍历

• 首先通过第一次循环，获得当前链表的长度size
• 然后运用数学计算的方式，得到倒数第n个结点正数时的索引（size - n）
• 得到指定元素正数位置后，找到前一个结点，断开其连接即可完成删除操作

双指针法

1. 首先让fast和slow指针都指向虚拟头结点

2. 先让fast往前走n+1个位置（和slow相隔n个结点）

3. slow和fast同时后移，直到fast为null

这时fast已经到链表尾部了，而slow和它相隔n个结点

也就是从后往前，slow指向的位置是倒数第n个元素的前一个结点

4. slow.next = slow.next.next，断开连接，完成删除操作

代码实现

双重遍历

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(-1, head);
        int size = 0;
        while(head != null){        // 获取链表大小
            size++;
            head = head.next;
        }
        ListNode p = dum;
        for(int i = 0; i < size - n; i++){        // 查找被删结点的前结点
            p = p.next;
        }
        p.next = p.next.next;        // 删除元素
        ListNode res = dum.next;    // 返回头结点
        return res;
    }
}

双指针法

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(-1, head);
        ListNode slow = dum, fast = dum;
        while(n-- >= 0){     // 让fast和slow之间相距n个结点
            fast = fast.next;
        }
        while(fast != null){        // 将slow指向被删除的上一个结点
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dum.next;
    }
}

总结

• 使用虚拟头结点可以将首结点由特殊位置转变为一般位置，简化操作。（否则需要对首结点做特殊处理）
• 涉及到指针操作时，都可以考虑考虑双指针法，配合图解更容易理解一些