删除链表的倒数第N个节点（Python and C++解法）

题目：

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

示例：

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

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

给定的 n 保证是有效的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

思路：

　　采用双指针，前面的指针比后面的指针先多走N+1个节点，当前面的指针到达None时，后面的指针所在位置的下一个节点就是要被删除的位置。

Python解法：

 1 class ListNode:  # 定义单链表
 2     def __init__(self, x):
 3         self.val = x
 4         self.next = None
 5 
 6 class Solution(object):
 7     @staticmethod
 8     def remove_nth_from_end(head: ListNode, n: int) -> ListNode:
 9         dummy = ListNode(0)
10         dummy.next = head
11         first = dummy  # 由于条件可能是链表有N个节点，删除倒数第N个节点，所以双指针应指向dummy
12         second = dummy
13         for i in range(n+1):  # 考虑到删除节点后需要重接链表，所以前面的指针先走n+1步
14             first = first.next
15         while first is not None:
16             first = first.next
17             second = second.next
18         second.next = second.next.next
19         return dummy.next  # head有可能被删除，因此不能返回head

C++解法：

 1 struct ListNode {  // 定义单链表
 2     int val;
 3     ListNode *next;
 4     ListNode(int x) : val(x), next(NULL) {}
 5 };
 6 
 7 class Solution {
 8 public:
 9     ListNode *removeNthFromEnd(ListNode *head, int n) {
10         ListNode *dummy = new ListNode(0);  // 动态分配一个结构体对象作为哨兵节点
11         dummy->next = head;
12         ListNode *First = dummy;  // 由于条件可能是链表有N个节点，删除倒数第N个节点，所以双指针应指向dummy
13         ListNode *Second = dummy;
14         for (int i = 0; i <= n; i++)   // 考虑到删除节点后需要重接链表，所以前面的指针先走n+1步
15             First = First->next;
16         while(First != NULL) {
17             First = First->next;
18             Second = Second->next;
19         }
20         Second->next = Second->next->next;  // 重新连接链表
21         return dummy->next;
22     }
23 };