新网网站模板收录网站排名

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

题目：

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

分析：

要删除倒数第几个节点，那么我们需要怎么做呢？我们需要定义两个指针，快指针和慢指针，让快指针先走n步，再让慢指针和快指针一起往后走。

那么什么时候停止呢？当fast指针指向最后一个节点时（fast.next()==null）时停止，此时slow指针指向的就是 size - n个元素即倒数第 n + 1个元素，所以我们可以使用倒数 n + 1 个元素来删除倒数第 n 个元素。

比如一共有8个元素（1，2，3，4，5，6，7，8），当我们要删除倒数第2个元素，即7：

1. 先让 fast 走两步，0+2=2；
2. 再让 slow 和 fast 一起走，当 fast 再走了 6 步后达到了末尾 (8)，此时 slow 达到了(6)那么现在slow在的位置是倒数第3个位置。

代码：

/*** 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 dummyNode = new ListNode(0, head);ListNode fast = dummyNode, slow = dummyNode;for(int i = 0; i < n; i++){fast = fast.next;}while(fast.next != null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummyNode.next;}
}