Leetcode-19. Remove Nth Node From End of List

问题：

分析

单向链表的优点是插入、删除操作方便，不需要移动大量的元素，缺点在于查找没有数组方便。
并且本题需要从后往前逆序查找，单项链表很难实现。
解决办法：翻转链表，从而变逆序查找为顺序查找！！！因此，本题的算法复杂度为两次翻转链表的时间复杂度，加上查找第n个结点的时间复杂度，由于翻转和查找都为线性时间复杂度，所以时间复杂度为O(n);

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* ReverseList(ListNode *head)
    {
        ListNode* p,*q,*r;
        p = head;
        q = head->next;
        head->next = NULL;
        while(q)
        {
            r = q->next;
            q->next=p;
            p = q;
            q =r;
        }
        head = p;
        return head;
    }
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //reverse list 
        ListNode *pre,*p;
        head = ReverseList(head);//reverse list
        //find n-th node
        int count =1;
        
        p = head;// p ponits to head node
        if(p->next ==NULL)//只有一个元素
            return NULL;
        if(n == 1)
        {
            return ReverseList(head->next);
        }  
        while(p && n!=count)
        {
            pre = p;
            p = p->next;
            count++;
        }
        pre->next = p->next;
        
        //after delete the node,reverse back
        head = ReverseList(head);
        return head;
        

        
    }
};