LeetCode 删除链表的倒数第N个节点（O(n) + 图解）

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
算法思路：基本思路就是先便利一边得到链表的长度，然后进行计数移动length - n个节点，在进行删除。

ListNode* removeNthFromEnd(ListNode* head, int n) {
	if (head == NULL) {
		return NULL;
	}
	ListNode *ptr = head;
	ListNode *deletePtr = NULL;
	int length = 0;
	//首先一趟扫描确认链表的长度
	while (ptr != 0) {
		ptr = ptr->next;
	}
	ptr = head;//重置ptr
	//如果是需要删除头结点
	if (length == n) {
		deletePtr = head;
		head = head->next;
	}
	else {
		//移动length - n - 1个节点，因为prt起始节点为head
		for (int count = 1; count < length - n; ++count) {
			ptr = ptr->next;
		}
		deletePtr = ptr->next;
		ptr->next = ptr->next->next;
	}
	delete ptr;
	return head;
}

下面介绍一种一趟删除法，即进行一趟扫描就将倒数第n个删除。采用双指针法，前指针和后指针的间距为n，这样当后指针移动到尾端时，前指针移动到的位置正好为倒数第n-1即需要删除节点的前一个节点的位置。

ListNode* removeNthFromEnd(ListNode* head, int n) {
	if (head == NULL) {
		return NULL;
	}
	ListNode *end = head;//尾指针
	ListNode *deleteBefore = NULL;//倒数第n个前的指针,初始化为NULL
	//尾指针先移动n-1个节点(因为初始就在head处)
	while (n > 1) {
		end = end->next;
		--n;
	}
	//两个指针同时移动，保持间距为n，当end移动到尾端时，此时deleteBefore为待删除的倒数第n前的指针
	while (end != NULL && end->next != NULL) {
		end = end->next;
		if (deleteBefore == NULL) {
			deleteBefore = head;
		}
		else {
			deleteBefore = deleteBefore->next;
		}
	}
	ListNode *deletePtr = NULL;
	//删除的是表头
	if (deleteBefore == NULL) {
		deletePtr = head;
		head = head->next;

	}
	else {
		deletePtr = deleteBefore->next;
		deleteBefore->next = deleteBefore->next->next;
	}
	//释放节点
	delete deletePtr;
	return head;
}

如果实在不知道指针是如何移动，建议在纸上进行画图演示。