题目链接：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个元素（n总是有效的），不过要求遍历1次链表。

这道题的思路比较简单，采用快慢指针，先用快指针f从头后移n次，这样f就比慢指针s快了n个节点，然后f和s同时后移，直到f到达链表尾部，此时，s即为要删除的节点。

不过在处理链表的时候，有个小技巧，就是先给链表加头，这样就可以把链表的head节点也当成普通节点处理。而在加了头之后，就需要判断f的next是否到达链表尾部，当f的next到达链表尾部是，s的next刚好为要删除的节点，这样也方便删除节点。

时间复杂度：O(n)

空间复杂度：O(1)

======

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution 
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) 
    {
        ListNode *h = new ListNode(0);
        h -> next = head;
        
        ListNode *f = h, *s = h;
        while(n --)
            f = f -> next;
        while(f -> next != NULL)
        {
            f = f -> next;
            s = s -> next;
        }
        s -> next = s -> next -> next;
        
        return h -> next;
    }
};

说明一下，好多的链表题目都需要用采用双指针（或者说快慢指针）处理，像是判断链表是否有环、找链表中出现环的位置、找两链表的交点等等。。。