19. Remove Nth Node From End of List

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

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.

Follow up:

Could you do this in one pass?

---

给定一个链表，要求删除倒数第n个元素。我想到的做法是遍历一遍链表，同时把链表每个元素保存到一个数组中，遍历完之后就知道链表长度，这样就可以计算出倒数第n个元素是哪个元素，然后直接删掉即可。 代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        if (head->next == NULL)
            return NULL;
        vector<ListNode*> nodes;
        ListNode* ln = head;
        while (ln) {
            nodes.push_back(ln);
            ln = ln->next;
        }
        int target = nodes.size() – n;
        if (target == 0) {
            head->next = NULL;
            head = nodes[target + 1];
        }
        else if (target == nodes.size() – 1) {
            nodes[target – 1]->next = NULL;
        }
        else {
            nodes[target – 1]->next = nodes[target + 1];
        }
        return head;
    }
};

本代码提交AC，用时8MS。一看排名倒数，肯定还有更高效的算法，因为这种解法需要保存链表，而且是用vector.push_back的，所以肯定耗时。看题解，原来这是典型的快慢指针题，我这个非ACMer还是反应迟钝呀。

我们维护一个快指针和慢指针，初始的时候快慢都在起点，然后快指针先跑n步，此时快慢指针的距离为n，然后快慢指针同时跑，这样就能保持距离为n，当快指针到达末尾(NULL)的时候，慢指针刚好是在倒数第n的位置，真是巧妙。
但是为了删除倒数第n个节点，需要知道其前一个节点，所以让快指针到达NULL的前面位置停，即faster->next==NULL的时候停下来。
完整代码如下：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n)
    {
        if (head == NULL || head->next == NULL)
            return NULL;
        ListNode *slower = head, *faster = head;
        while (n–) {
            faster = faster->next;
        }
        if (faster == NULL)
            return head->next;
        while (faster->next) {
            faster = faster->next;
            slower = slower->next;
        }
        slower->next = slower->next->next;
        return head;
    }
};

本代码提交AC，用时4MS，果然快了不少。