题目地址

https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

题目描述

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

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 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 beforeHead = new ListNode(0, head);
        // beforehead -> 1 -> 2 -> 3 -> 4 -> 5 -> null
        //               5    4    3    2    1     0

        // 1. 定义两个节点，使其相距 (n+1) 个节点
        // beforeDeleteNode 是要删除的节点的前一个节点
        ListNode beforeDeleteNode = beforeHead;
        ListNode nullNode = head;
        for (int i = 0; i < n; ++ i) {
            nullNode = nullNode.next;
        }

        // 2. 同时移动 beforeDeleteNode 和 nullNode
        while (nullNode != null) {
            beforeDeleteNode = beforeDeleteNode.next;
            nullNode = nullNode.next;
        }

        // 3. 删除 beforeDeleteNode.next 节点
        if (beforeDeleteNode.next != null) {
            beforeDeleteNode.next = beforeDeleteNode.next.next;
        }
        return beforeHead.next;
    }
}

因为是单链表，所以要删除一个节点的话，需要从待删除节点的前一个节点删除。
因此，定义两个间隔 n+1 的双指针。

复杂度分析：

• 时间复杂度 O(n)，n 为链表的长度。
• 空间复杂度 O(1)