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

### 题目地址(19. 删除链表的倒数第 N 个节点)

<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 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

```

### 前置知识

* 链表
* 双指针

### 公司

* 阿里
* 百度
* 腾讯
* 字节

### 思路

这里我们可以使用双指针算法，不妨设为指针 A 和 指针 B。指针 A 先移动 n 次， 指针 B 再开始移动。当 A 到达 null 的时候， 指针 B 的位置正好是倒数第 n。这个时候将 B 的指针指向 B 的下下个指针即可完成删除工作。

算法：

* 设置虚拟节点 dummyHead 指向 head（简化判断，使得头结点不需要特殊判断）
* 设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
* 移动 q，直到 p 与 q 之间相隔的元素个数为 n
* 同时移动 p 与 q，直到 q 指向的为 NULL
* 将 p 的下一个节点指向下下个节点

![19.removeNthNodeFromEndOfList](https://p.ipic.vip/gn0tx0.gif)

(图片来自： <https://github.com/MisterBooo/LeetCodeAnimation>)

### 关键点解析

1. 链表这种数据结构的特点和使用
2. 使用双指针
3. 使用一个 dummyHead 简化操作

### 代码

代码支持: JS, Java，CPP

Javascript Code:

```js
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  let i = -1;
  const noop = {
    next: null,
  };

  const dummyHead = new ListNode(); // 增加一个dummyHead 简化操作
  dummyHead.next = head;

  let currentP1 = dummyHead;
  let currentP2 = dummyHead;

  while (currentP1) {
    if (i === n) {
      currentP2 = currentP2.next;
    }

    if (i !== n) {
      i++;
    }

    currentP1 = currentP1.next;
  }

  currentP2.next = ((currentP2 || noop).next || noop).next;

  return dummyHead.next;
};
```

Java Code:

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        TreeNode dummy = new TreeNode(0);
        dummy.next = head;
        TreeNode first = dummy;
        TreeNode second = dummy;

        if (int i=0; i<=n; i++) {
            first = first.next;
        }

        while (first != null) {
            first = first.next;
            second = second.next;
        }

        second.next = second.next.next;

        return dummy.next;
    }
}
```

CPP Code:

```cpp
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *p = head, *q = head;
        while (n--) q = q->next;
        if (!q) {
            head = head->next;
            delete p;
            return head;
        }
        while (q->next) p = p->next, q = q->next;
        q = p->next;
        p->next = q->next;
        delete q;
        return head;
    }
};
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/h9nm77.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/19.removenthnodefromendoflist.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.