用单指针删除单链表中倒数第k个结点

题目描述：

给定一个单链表的头指针和倒数第 k 个结点，要求在单链表中删除该倒数第 k 个结点，并返回删除后的单链表的头指针。

例如，给定单链表为 1->2->3->4->5，倒数第 2 个结点为 4，那么删除该结点后的单链表为 1->2->3->5。

解题思路：

双指针法。可以定义两个指针 slow 和 fast，初始时两个指针同时指向头结点。让 fast 先向前走 k 步，然后 slow 和 fast 同时开始向前走，直到 fast 指向尾结点。

此时，slow 指向的结点就是倒数第 k 个结点的前一个结点。然后我们只需要将 slow 指向的结点的下一个结点删除即可。

需要注意，如果删除的是头结点，那么需要将头指针向后移动一个位置。

代码实现：

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

ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *slow = head, *fast = head;

// fast 先向前走 k 步
for (int i = 0; i < n; i++) {
fast = fast->next;
}

// 如果 fast 为空，说明删除头结点
if (!fast) {
ListNode *tmp = head;
head = head->next;
delete tmp;
return head;
}

// slow 和 fast 同时向前走
while (fast->next) {
slow = slow->next;
fast = fast->next;
}

// 删除 slow 指向的结点的下一个结点
ListNode *tmp = slow->next;
slow->next = slow->next->next;
delete tmp;

return head;
}