# 19. Remove Nth Node From End of List 删除链表的倒数第 N 个结点

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客：http://fuxuemingzhu.cn/open in new window
• 个人公众号：负雪明烛
• 本文关键词：链表, 删除节点，双指针，题解，leetcode, 力扣，Python, C++, Java

@TOC

## # 题目描述

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:

1. Given n will always be valid.

• Could you do this in one pass?

## # 解题方法

### # 双指针

Python代码如下：

``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
def removeNthFromEnd(self, head, n):
"""
:type n: int
:rtype: ListNode
"""
root = ListNode(0)
fast, slow, pre = root, root, root
while n - 1:
fast = fast.next
n -= 1
while fast.next:
fast = fast.next
pre = slow
slow = slow.next
pre.next = slow.next
return root.next

``````

C++代码如下：

``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
ListNode* prev = dummy;
ListNode* cur = dummy;
while (n--) {
cur = cur->next;
}
while (cur && cur->next) {
cur = cur->next;
prev = prev->next;
}
prev->next = prev->next->next;
return dummy->next;
}
};
``````

## # 日期

2018 年 6 月 23 日 —— 美好的周末要从刷题开始 2019 年 1 月 10 日 —— 加油 2019 年 9 月 27 日 —— 昨天面快手，竟然是纯刷题