19. 删除链表的倒数第N个节点
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
解法1：两次遍历，单指针
第一遍遍历计算长度，第二遍删除节点，倒数第N个，就是正数第len-N+1个，即找第len-N个节点完成删除操作，站在第一个节点上，只需走len-N-1步。
class Solution {int listLen(ListNode* head) {if (NULL == head)return 0;int len = 0;while (head) {++len;head = head->next;}return len;}
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if (NULL == head || n < 0)return head;int len = listLen(head);if (len < n)return head;else if (len == n)return head->next;n = len - n - 1;ListNode *first = head, *tmp;while (n--)first = first->next;tmp = first->next->next;delete(first->next);first->next = tmp;return head;}};解法2：一次遍历，双指针，无哨兵
无法计算长度，用双指针一个先走，一个后走，重点在于先走的指针走几步，后面的指针再走。考虑到有可能需删首节点，所以需要特殊处理这种情况。
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if (head == NULL || n <= 0)return head;ListNode* first = head, *second = head; //两指针都在head上while (n-- && first) //以first要停的位置推需要在首节点上先走n步first = first->next;while (first && first->next) { //first要停在最后一个非空节点上first = first->next;second = second->next;}if (n > 0 && NULL == first) //n大于链表长度return head;ListNode *tmp;if(first) { //first如愿，得到目标删除节点的前一节点secondtmp = second->next->next;delete second->next;second->next = tmp;return head;} else { //否则，需要删除头结点tmp = head->next;delete head;return tmp;}}
};解法3：一次遍历，双指针，有哨兵
考虑到有可能需删首节点，用哨兵处理这种情况。
class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {if (NULL == head || n <= 0)return head;ListNode dummy(0);dummy.next = head;ListNode *first = &dummy, *second = &dummy; //起始点是哨兵节点while (n-- && first)first = first->next;if (n > 0 && NULL == first)return head;while (first && first->next) { //first要停在最后一个非空节点上first = first->next;second = second->next;}first = second->next->next;delete second->next;second->next = first;return dummy.next;}
};可能有细心的同学会发现，该实现跟解法2没有哨兵实现相比，两指针的起点不一样，实际上将上续实现中指针初始化改为ListNode *first = head, *second = head;，无需修改其他依旧是正确的。因为second和first起点一样，first少走一步，second也少走一步，所以second之后同步走的时候，这一步的差就一起携手走完了，重点是两个指针的相对步数差，而不是两个指针的起点。
用哨兵实现会相对简单易懂，建议使用哨兵，少出错，程序可读性高。注意哨兵的细节处理和垃圾回收。