[LeetCode] Remove Nth Node From End of List

 

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()函数删除的是参数后面的那个节点，当要删除的节点是第一个节点时，它没有前面的节点，因此要分开处理。

补充：软件开发 , C++ ,