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

要做到时间复杂度O(N)，空间复杂度O(1)

就只有一次遍历然后不保存整个链表。

因为已知必定有解，所以可以存两个节点，相距n，然后依次推进，当大的节点next==null，说明小的节点就是要求的节点。

注意考虑头结点被删除的情况

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode*l,*r;
        ListNode* tp;
        l=head;
        tp=l;
        r=l;
        for(int i=0;i<n-1;i++)
        {
            r=r->next;
        }
        while(r->next!=NULL)
        {
            tp=l;
            l=l->next;
            r=r->next;
        }
        if(l==head)
            return head->next;
        
        tp->next=tp->next->next;
        return head;
    }
};