2018-06-27 19. Remove Nth Node F

题意：给你一个单项链表和一个值n，将倒着数第n个节点删除后，返回head指针。题意要求最好只遍历链表一遍。
解题思路：
思路一：定义一个全局变量cnt，使用递归调用，找到最后一个节点，每返回一个节点cnt就加一，如果cnt等于n那么就是倒数第n个节点，返回第n个节点的next成员。
但这么操作貌似还是两次遍历，递归到最后一个节点是一次。返回到第一个节点又一次。
思路二：定义一个计数指针l1，从头开始计数到n，则说明当前l1是正数第n个node的next值，这时另一个指针l2开始和该计数指针l1一起遍历，当计数指针l1遍历到最后一个节点的next时，l1指针正好指的是倒数第n个节点。
在使用指针是，l1 可以是ListNode格式的，由于l2要修改原始链表中的数据，所以l2要用ListNode*格式。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *l1 = head, **l2 = &head;
        for(int i = 0; i < n; i++)
            l1 = l1->next;     //计数到n，此时l1等于第n个指针的next成员。
        while(l1){             //只有当l1为空时，l2才是指向倒数第n个node的指针的地址
            l1 = l1->next;
            l2 = &((*l2)->next);
        }
        *l2 = (*l2)->next;    //把指向倒数第n个node的指针的值改为指向倒数下一个node
        return head;
    }
};

有两点可以学习：
1、当遍历单向链表的时候，倒数第n个节点可以使用计数指针先遍历正数第n个节点，然后一起“遍历指针从头遍历”+“计数指针继续遍历”的方式，当计数指针遍历完整个链表就是遍历指针指向倒数第N个节点的时候。
2、当要修改链表中某节点的next成员指针的值时，可以使用ListNode** 来存储指向node的指针的地址，直接使用 l2 = (l2)->next;的方式遍历链表，然后修改链表中任何想修改的指针的值。