19. Remove Nth Node From End of List

Given a linked list, remove the nth node from the end of list and return its head.

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个节点；

写一个函数来确定要删除的是第几个节点，方法是获取链表总长度len，那么我们要删除的就是第 nth = len - n 个节点；
知道了要删除的节点是第几个以后，我们只需要在指针head指向待删除节点的前一个节点地址时，将指针的next指向next的next地址就可以了：
即：head->next = head->next->next；
好了，思路确定好了以后我们来分析下边界值：

1. 当待删除的节点是第一个节点时(n = len)：
   待删除节点不存在前一个节点，我们只需要返回头指针的 next ；
   即：return head->next;
2. 当不删除节点时(n = 0)：
   不存在待删除节点，也就没有 head->next->next；直接返回head即可；

My Solution（C/C++完整实现）：

#include <cstdio>
#include <iostream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

int getNthFromHead(ListNode *head, int n) {
    int len = 0;
    while (head) {
        len += 1;
        head = head->next;
    }
    return len - n;
}

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *result = head;
        if (n == 0) {
            return result;
        }
        int nth = getNthFromHead(head, n);
        if (nth == 0) {
            return result->next;
        }
        while (nth - 1) {
            head = head->next;
        nth -= 1;
        }
        head->next = head->next->next;
        return result;
    }
};

int main() {
    ListNode a(1);
    ListNode b(2);
    ListNode c(3);
    ListNode d(4);
    ListNode e(5);
    ListNode f(6);
    ListNode g(7);
    a.next = &b;
    b.next = &c;
    c.next = &d;
    d.next = &e;
    e.next = &f;
    f.next = &g;
    Solution s;
    ListNode *result = s.removeNthFromEnd(&a, 3);
    while (result) {
        printf("%d->", result->val);
        result = result->next;
    }
    return 0;
}

结果：

1->2->3->4->6->7->

My Solution:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head, n):
        """
        :type head: ListNode
        :type n: int
        :rtype: ListNode
        """
        l = head
        num = self.getNumFromHead(head, n)
        if num == 0:
            return l.next
        nth = 0
        while head:
            nth += 1
            if nth == num:
                next = head.next
                head.next = next.next
                return l
            head = head.next
                 
    def getNumFromHead(self, head, n):
        num = 0
        while head:
            num += 1
            head = head.next
        return num - n