删除链表中倒数第n个节点（LintCode）

题目来源：LintCode

原题地址：http://www.lintcode.com/zh-cn/problem/remove-nth-node-from-end-of-list/

题目：

给定一个链表，删除链表中倒数第n个节点，返回链表的头节点。

您在真实的面试中是否遇到过这个题？

Yes

样例

给出链表1->2->3->4->5->null和 n = 2.

删除倒数第二个节点之后，这个链表将变成1->2->3->5->null.

注意

链表中的节点个数大于等于n

挑战

O(n)时间复杂度

难度级别：
容易

思路分析：
采用双指针的方式来解此题，会很容易。
设置两个指针，其一先走n步，然后二者再一起走，知道先走的指针到达链表的末尾为止。

实现代码：

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution
{
public:
    /**
    * @param head: The first node of linked list.
    * @param n: An integer.
    * @return: The head of linked list.
    */
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        if (head == NULL)
        {
            return head;
        }
        ListNode *myHead = new ListNode(0);
        myHead->next = head;
        ListNode *p = myHead;
        ListNode *q = myHead;
        
        for (int i = 0; i < n; i++)
        {
            p = p->next;
        }
        while (p->next != NULL)
        {
            p = p->next;
            q = q->next;
        }
        p = q->next;
        q->next = q->next->next;
        free(p);
        return myHead->next;
    }
};

代码说明：
需要说明的是，在代码实现的过程中，我加入了一个头指针，这样能够使得原来的头指针变成普通指针，所执行的操作就变成统一的了。
这是很方便的。因为我不用再去判断是否是头指针了。