二分查找练习记录：

19.删除链表的倒数第 N 个结点力扣

题目描述：

删除单向链表的倒数第 N 个结点，例如：

输入：1->2->3->4->NULL
删除倒数第二个节点，即删除节点3
输出：1->2->3->NULL

思路：

方法一：先遍历链表，得到节点数，正向遍历到要删除节点的前一个节点

方法二：双指针，只要两个指针的间隔为n，就可以找到要删除节点的前一个节点，这里为了方便头节点的处理，使用了一个虚拟头结点。将两个指针，first，second同时指向虚拟节点，让first节点先走n个节点使得两个节点的间隔为n，让后两个节点同时往后走，直到first节点到链表尾部（NULL），此时second节点位于待删除节点的前一个节点。

代码实现：

#include
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/
struct ListNode {
	int val;
	struct ListNode *next;
};

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
	int loopNum = 0;
	int sum = 0;
	struct ListNode* node =  head;

	while (node != NULL)
	{
		node = node->next;
		sum++;
	}
	if ((head != NULL )&&( sum ==1) &&  (n == 1))
	{
		return NULL;
	}
	if (sum == n)
	{
		head = head->next;
		return head;
	}
	node = head;
	for (loopNum;loopNum<(sum-n-1);loopNum++)
	{
		node = node->next;
	}
	node->next = node->next->next;

	return head;
}
struct ListNode* removeNthFromEnd1(struct ListNode* head, int n) {
		struct ListNode* dummy = malloc(sizeof(struct ListNode));
		dummy->val = 0, dummy->next = head;
		struct ListNode* first = dummy;
		struct ListNode* second = dummy;
		for (int i = 0; i <= n; ++i) {
			first = first->next;
		}
		while (first) {
			first = first->next;
			second = second->next;
		}
		second->next = second->next->next;
		struct ListNode* ans = dummy->next;
		free(dummy);
		return ans;
	
}

int main()
{
	struct  ListNode node3;
	node3.val = 3;
	node3.next = NULL;
	struct  ListNode node2;
	node2.val = 2;
	node2.next = &node3;
	struct  ListNode  node1;
	node1.val = 1;
	node1.next = &node2;
	struct  ListNode*   result = removeNthFromEnd1(&node1,2);
	while (result != NULL)
	{
		printf("val = %d", result->val);
		result = result->next;
	}
	return 0;
}