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

链表的长度

用到哑节点
遍历到 L−n+1 个节点时，它的下一个节点就是我们需要删除的节点，只需要修改一次指针，就能完成删除操作。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;//知道要删除的节点的前一个
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;//保留最开始位置
        return ans;
    }
    public int getLength(ListNode head) {
        int length = 0;
        while (head != null) {
            ++length;
            head = head.next;
        }
        return length;
    }
}

双指针、

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;//双指针错开一个位置.
        ListNode second = dummy;//
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {//退出循环时first指向null.
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}