刷刷刷Day4|19.删除链表的倒数第N个节点

19.删除链表的倒数第N个节点

LeetCode题目要求

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
示例：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

解题思路

根据题目要求，如删除倒数第二个节点，即是把 4 删除掉，那么原来 4 的前序节点的 next 节点需要指向 5， 所以这里的关键点在于记录被删除节点的前序节点就比较容易处理了
代码：

/**
 * 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(-1, head);

        //找到倒数 n 的那个节点，先遍历找到节点
        ListNode node = dummy;
        int size = 0;
        while (node != null) {
            size++;
            node = node.next;
        }
        //索引  0 1 2 3 4
        //元素 -1 1 2 3 4
        // size=5 删除倒数第二个 即 索引=3  size-2-1为前序节点
        // size - 2 - 1 = 5 - 2 - 1 = 2
        // 1 pre=1
        // 2 pre=2
        ListNode pre = dummy;
        int i = 1;
        while (i++ <= (size - n - 1)) {
            pre = pre.next;
        }

        // 被删除的节点为 pre.next
        ListNode delNode = pre.next;
        if (delNode != null) {
            pre.next = delNode.next;
        }
        return dummy.next;
    }
}

快慢指针解法，这个比较巧妙，通过两个指针，找到要删除节点的前序节点。
通过让两个指针，一个指向被删除的前序节点，一个指向尾节点null
这里同时要借助于 dummy 节点，操作起来就比较方便了。参看下图的说明，要理解这个思路，建议看最后一步，然后往前推，思考为什么要这样做

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 利用虚拟节点。这样就不需要考虑是否是头节点的问题
        ListNode dummy = new ListNode(-1, head);

        // 两个指针，一个 slow， 一个 fast
        ListNode slow = dummy;
        ListNode fast = dummy;
        // fast 先移动 n 步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        slow.next = slow.next.next;
        
        return dummy.next;
    }
}

重难点

巧妙的使用快慢两个指针，充分利用虚拟头节点
附：学习资料链接