For 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.
Try to do this in one pass.
问题描述：给定一个链表，从链尾开始算起，删除第n个节点，并返回链表头。
看到这题，我就想到了递归，因为不采用递归的话，就无法确定倒数第n个节点。采用递归，当遍历到链尾时就是0，最后一个节点就是1，依次类推。
class Solution {
public:
int listLen(ListNode *head)
{
ListNode *p = head;
int n = 0;
while(p) {
p = p->next;
++n;
}
return n;
}
int removenode(ListNode *head, int n)
{
if(head == NULL)
return 0;
int m = removenode(head->
next, n) + 1;
if(m == n + 1) {
ListNode *p = head->next;
head->next = p->next;
free(p);
}
return m;
}
ListNode *removeNthFromEnd(ListNode *head, int n) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
int len = listLen(head);
if(n == len) {
ListNode *p = head;
head = head->next;
free(p);
}
removenode(head, n);
return head;
}
};
在上面的解法中，主要有两种n需要区分，当删除的节点是第一个节点时，和删除的节点不是第一个节点时，这是因为，我的removenode()函数删除的是参数后面的那个节点，当要删除的节点是第一个节点时，它没有前面的节点，因此要分开处理。