删除链表倒数第N个节点：快慢指针，快指针先走

给你一个链表，删除链表的倒数第 n个结点，并且返回链表的头结点。

需求

• 输出倒数第n个数
• 返回头节点

实现

• 快慢指针

代码

class Solution {
    /**
     * 删除链表的倒数第 n 个结点，并返回头结点。
     *
     * @param head 链表头结点
     * @param n    倒数第 n 个结点
     * @return 删除后的链表头结点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
//        哨兵节点，处理头节点被删的情况
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 快指针先走 n+1 步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 快慢指针同时前进，直到快指针到达末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除倒数第 n 个结点
        slow.next = slow.next.next;

        return dummy.next;
    }
}

‍