删除链表的倒数第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即slowclass 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;}
}