14-链表练习-剑指 Offer II 021. 删除链表的倒数第 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符合规范，题目中不用判断其合法性）

进阶：能尝试使用一趟扫描实现吗？

---

思路

此题与上一题类似，采用快慢指针法。不同的是，此题的slow和fast两个快慢指针都是从dummyHead虚拟头节点开始向后走，这样可以确保当fast指向null时，slow恰好指向待删除节点的前一个节点，方便删除节点。

---

代码

/*** 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) {if(head == null) {return null;}ListNode dummyHead = new ListNode(-1);dummyHead.next = head;//采用快慢指针法先找到链表中倒数第n个节点ListNode slow = dummyHead, fast = dummyHead;//先让fast走n步for(int i = 0; i < n + 1; i++) {if(fast == null) {return head;}fast = fast.next;}//让slow和fast一起向后走while(fast != null) {slow = slow.next;fast = fast.next;}//此时slow就指向了待删除节点的前一个节点，删除要删的节点即可slow.next = slow.next.next;return dummyHead.next;}
}