删除链表的倒数第N个节点，剑指offerII（21）,力扣
目录
题目地址：
题目：
相似类型题：
我们直接看本题题解吧：
解题方法：
难度分析：
解题分析：
解题思路（双指针）：
代码实现：
代码说明：
代码实现（计算链表长度）：
代码实现（栈）：
题目地址：
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
难度：中等
今天刷删除链表的倒数第N个节点，大家有兴趣可以点上看看题目要求，试着做一下。
题目：
给定一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。
相似类型题：
强烈建议先做做这道题目，做完这道题，对下面题目的双指针解法会有更好的理解
链表中倒数第k个节点，剑指offer,力扣-CSDN博客
我们直接看本题题解吧：
解题方法：
方法1、计算链表长度（两次遍历，第一次求链表长度，第二次删除对应节点）
方法2、栈，（利用先进后出特点）
方法3、双指针（快慢指针）
难度分析：
总体上不是很难，主要是双指针的使用与理解
解题分析：
解题思路（双指针）：
1、创建亚节点dummy（充当虚头结点）,指向head
2、创建双指针,fast,slow,这里指针fast直接指向head，而指针slow需要指向被删除节点的上一个节点（不然被删节点后面节点也跟着被删了），因此需要初始化指向dummy节点
3、循环遍历，fast指针先走n步，然后fast与slow同步移动（此时二者相差n-1个节点），最后直到fast指向null，那么此时slow指向的是被删节点的前驱节点
4、最后返回链表，不过要注意是返回dummy.next即链表的第一个节点，如果返回head在特殊情况下会报错。
代码实现：
/**
* 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; }
* }
*/
//这里first即fast，second即slow
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head); //创建亚节点
ListNode first = head;
ListNode second = dummy;
for (int i = 0; i < n; ++i) {
first = first.next; //指针fast 先走n步
}
while (first != null) {
first = first.next;
second = second.next; //fast 与slow同步移动，直至 fast指向null
}
//被删节点的上一节点的next指向被删节点的下一节点，即删除节点操作
second.next = second.next.next;
ListNode ans = dummy.next;
return ans;//这里如果返回head的话，那么当链表只有一个元素并且删除一个元素的时候返回的不是空
}
}代码说明：
解题思路里讲的特殊情况，即链表只有一个元素时要删除这个元素，则会报错，所以保险起见，还是用设置头指针指向链表第一个结点的方式比较稳妥。
代码实现（计算链表长度）：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
int length = getLength(head);
ListNode cur = dummy;
for (int i = 1; i < length - n + 1; ++i) {
cur = cur.next;
}
cur.next = cur.next.next;
ListNode ans = dummy.next;
return ans;
}
public int getLength(ListNode head) {
int length = 0;
while (head != null) {
++length;
head = head.next;
}
return length;
}
}
代码实现（栈）：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0, head);
Deque<ListNode> stack = new LinkedList<ListNode>();
ListNode cur = dummy;
while (cur != null) {
stack.push(cur);
cur = cur.next;
}
for (int i = 0; i < n; ++i) {
stack.pop();
}
ListNode prev = stack.peek();
prev.next = prev.next.next;
ListNode ans = dummy.next;
return ans;
}
}