# LeetCode19. Remove Nth Node From End of List（链表 / 模拟）

## LeetCode19. Remove Nth Node From End of List（链表 / 模拟）

• Medium
• Accepted：356,264
• Submissions：1,047,909

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Could you do this in one pass?

### 链接

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

### 题解

（吐槽一下，实际上后移应该是往前移，不过我这么说习惯了）

### 代码

• Runtime: 8 ms, faster than 100.00% of C++ online submissions for Remove Nth Node From End of List.
• Memory Usage: 9.8 MB, less than 11.70% of C++ online submissions for Remove Nth Node From End of List.
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {

for (int i = 0; i < n + 1; ++i) // 后移
q = q->next;
while (q)
{
p = p->next;
q = q->next;
}

ListNode* delNode = p->next; // 真删除结点
p->next = delNode->next;
delete delNode;

ListNode* retNode = virtualHead->next; // 删除

return retNode;
}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyNode = new ListNode(-1);

ListNode* low = dummyNode;
ListNode* fast = dummyNode;

for (int i = 0; i < n; ++i)
fast = fast->next;
// 这里为了让 low 指向要删除节点的上一个节点，再往后走一步
fast = fast->next;

while (fast != NULL)
{
fast = fast->next;
low = low->next;
}

ListNode* deleteNode = low->next;
low->next = deleteNode->next;
delete deleteNode;

};