卷进大厂系列之LeetCode刷题笔记：删除链表的倒数第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
涉及知识点
链表是由节点组成的，在链表的每个节点中，由两部分组成，即数据域（存放数据）和指针域（指向下一个节点的指针）；
- 链表不能像数组一样可以直接定位元素位置，所以它不能通过直接定位来删除元素
那么根据题目我们可以提炼出的关键点：
- 我们删除的是链表中倒数的第n个节点，从后往前数的第n个
- 1 <= n <= sz，不用判断n会大于链表长度的特殊情况
解决这道题目的关键点是找出来需要删除的节点，因为链表并不像数组一样直接定位删除，这样就很简单，所以链表这个只能一个一个的找，但是又因为这是倒数的第n个（要不然可就对不起中等难度了），所以不能说直接从前向后遍历n个元素，不过从后向前遍历也不行呀，因为你不知道最后的哪个是多少。。。
综上分析，要想删除倒数第n个元素，我们还得想办法从前向后遍历，这样可以用head节点，然后依次遍历，下面提供两种方法解决这个题目。
题目解答
Java解法一
将从后向前遍历转成从前向后的遍历
- 计算出链表的长度Length
- 根据长度关系，得出删除倒数第n个，就是删除正数第Length-n+1个
- 利用链表的删除，删除正数第Length-n+1个元素
根据以上分析，实现代码如下：
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummyhead = new ListNode(0,head); //虚拟头节点 //获取链表的长度 int Length = 0; //初始化链表的长度 while(head.next != null){ Length += 1; head = head.next; //往后遍历 } //删除倒数第n个，就是删除正数第Length-n+1个 ListNode cur = dummyhead; for(int i = 0; i < Length-n+1; ++i){ //注意是++i,不是i++ cur = cur.next; } //删除操作 cur.next = cur.next.next; //返回结果 ListNode ans = dummyhead.next; return ans; }}
Java解法二
使用双指针的方法
- 定义两个指针，分别为快慢指针（用来将倒数第n个转化为从前向后遍历）
- 让快指针先移动 n+1个位置，然后快慢指针一起移动，这样就实现了当快指针为null的时候，快慢指针相差的位置是n+1，也就是说此时的慢指针的下一个位置就是需要删除的节点了
- 利用链表删除的特点，删除慢指针的下一个节点
根据以上分析，实现代码如下：
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { //使用双节点的方式 ListNode dummyhead = new ListNode(0); dummyhead.next = head; ListNode fast = head; //定义快指针 ListNode slow = head; //定义慢指针 while(n > 0 && fast != null){ //让快指针先向后移动n个长度，用来实现倒数第n个 fast = fast.next; n--; } // 如果快指针走到了最后说明删除的是第一个节点,就返回head.next就好 if(fast==null){ return head.next; } fast = fast.next; //fast往后移动一个位置，这样就就可以使得慢指针下一个位置就是需要删除的节点，即利用链表删除的特点 while(fast != null){ //让快慢指针一起移动，然后当快节点到达链尾时，慢指针下一个位置就是需要删除的节点 fast = fast.next; slow = slow.next; } //删除节点（慢指针的下一个位置） slow.next = slow.next.next; return dummyhead.next; }}
