删除链表的倒数第N个结点--LeetCode

题目

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

思路一：计算链表长度

我们首先从头节点开始对链表进行一次遍历，得到链表的长度 L。随后我们再从头节点开始对链表进行一次遍历，当遍历到第 L−n+1 个节点时，它就是我们需要删除的节点。

为了与题目中的 n 保持一致，节点的编号从 1 开始，头节点为编号 1 的节点。

为了方便删除操作，我们可以从哑节点开始遍历 L−n+1 个节点。当遍历到第 L−n+1 个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。

/*** 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(0,head);//创建虚拟节点，直接将其放在头结点前int length = getLength(head);//调用getLength算法来对链表进行计算链表长度ListNode cur = dummy;//定义当前指针for(int i = 1;i < length - n + 1;i++){//下标从1开始，结束在下标倒数n之前一位cur = cur.next;}cur.next = cur.next.next;//直接删除return dummy.next;//返回虚拟节点下一个}public int getLength(ListNode head){//计算链表长度算法int length = 0;while(head != null){//结束条件为当前节点为空++length;head = head.next;}return length;}
}

思路二：栈

我们也可以在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 n 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。这样一来，删除操作就变得十分方便了。

/*** 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(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++){//删除倒数第N个结点,i=0到n-1stack.pop();//弹出栈的顶部}ListNode prev = stack.peek();//倒数第N个结点的前一个结点prev.next = prev.next.next;//直接删除return dummy.next;}
}