本文共 1291 字，大约阅读时间需要 4 分钟。

给你一个链表，删除链表的倒数第 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

思路：

由于有可能要删除的是倒数最后一个结点，也即第一个结点，故我们可以建立一个虚拟头结点dummy，然后设定快慢指针，fast和slow，让fast先走n步，slow不动，然后fast和slow同时走，直到fast走到尽头，假设共有m个结点，则fast走n步后，还剩下m-n个结点，此时fast和slow再都走m-n步，fast到达尽头，而slow还差n步才到尽头，而这个位置刚好是我们所要删除结点的前一位置。如图所示：

Java代码

/** * 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) {
           //由于可能要删除的是头结点，故建立虚拟头结点，用于统一操作        ListNode dummy = new ListNode(-1);        dummy.next = head;        ListNode fast = dummy,slow = dummy;        //快指针先走n步        for(int i = 0;i < n;i++){
               fast = fast.next;        }        //现在快慢指针一起走        while(fast.next != null){
               slow = slow.next;            fast = fast.next;        }        slow.next = slow.next.next;        return dummy.next;    }}

转载地址：https://blog.csdn.net/YouMing_Li/article/details/113405407 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！