删除链表的倒数第N个节点

题意

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

数据结构

以下为leetcode的本身代码部分，需要注意的是，函数接口removeNthFromEnd(ListNode* head, int n)的参数head为链表的第一个元素。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {

    }
};

解题思路

在链表的开始，使用两个指针skip_p和pre_p分别指向头部，先让skip_p指针先走n步，然后让skip_p、pre_p指针一起走，等到skip_p指针走到末尾，pre_p指针便是所要删除的指针。
此外，需要在head指针前面增加一个假头部指针的原因：

1. 由于是单链表的数据结构，因此实际需要的是pre_p指针指在待删除指针的前一个指针。
2. 头部为第一个元素，为了代码的整洁，不要做特判，需要一个假头部pre_h。

 /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        /* 添加假头部，方便后面的代码处理，不用做特判 */
        ListNode* pre_h = new ListNode(0);
        pre_h->next = head;

        /* 先让指针skip_p走n步 */
        ListNode* skip_p = pre_h;
        while (skip_p->next != NULL && n > 0) {
            skip_p = skip_p->next;
            n--;
        }

        /* 两个指针一起走，等到skip_p->next为NULL，那么指针pre_p->next为待删除的指针 */
        ListNode* pre_p = pre_h;
        while(skip_p->next != NULL) {
            skip_p = skip_p->next;
            pre_p = pre_p->next;
        }

        /* 获取待删除的指针，从链表剔除并删除 */
        ListNode* del_p = pre_p->next;
        pre_p->next = del_p->next;
        delete del_p;

        /* 更新链表头部，删除假头部 */
        head = pre_h->next;
        delete pre_h;
        return head;
    }
};