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

给定一个链表，删除链表的倒数第 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 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

想法1：

只使用一趟扫描，想到用快慢指针的方法，只不过要注意几种特殊情况：

如果头结点为空或仅有头结点一个元素如果仅有两个元素而且删除第1个元素 class Solution { public: ListNode* removeNthFromEnd(ListNode* head, int n) { if(!head&&!head->next) return nullptr; ListNode* p1 = head, *p2 =head; while(n) { p1 = p1->next; n--; } if(!p1) return head->next; while(p1->next) { p1=p1->next; p2=p2->next; } p2->next = p2->next->next; return head;} };

之前试错：如果没有先判断p直接while(p1->next)是不可以的，因为p1有可能就是nullptr

想法二（递归）（给想到的大佬献上膝盖）

class Solution { public: int cur = 0; ListNode* removeNthFromEnd(ListNode* head, int n) { if(!head) return nullptr; head->next = removeNthFromEnd(head->next,n); cur++; if(cur==n)return head->next; return head; } };

cur设在函数外面，相当于全局变量了，每一个递归return，cur就+1，所以cur相当于逆序数。当cur==n时，返回head->next，再上一层，就等于head->next = head->next->next这就是核心。