LeetCode19题 删除链表的倒数第N个节点 (c++ 递归)
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
分析：用作双指针的话很简单，但这次用了递归的方法，时空复杂度都很感人。。。。。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: int cnt=0; bool remove(ListNode *&a,int count) { if(a->next==NULL||remove(a->next,count)) //注意边界的情况 cnt++; if(cnt==count) a=a->next; return true; } ListNode* removeNthFromEnd(ListNode* head, int n) { remove(head,n); return head; } };