19. 删除链表的倒数第 N 个结点

题目描述

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

 

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

解法

方法一：快慢指针

定义两个指针 fast 和 slow，初始时都指向链表的虚拟头结点 dummy。

接着 fast 指针先向前移动 n 步，然后 fast 和 slow 指针同时向前移动，直到 fast 指针到达链表的末尾。此时 slow.next 指针指向的结点就是倒数第 n 个结点的前驱结点，将其删除即可。

时间复杂度 O(n)，空间复杂度 O(1)。其中 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 ans = new ListNode(0,head);ListNode slow = ans;ListNode fast = head;while(fast != null && n>0){fast = fast.next;n--;}while(fast != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;ans = ans.next;return ans;}
}