Given a linked list, remove the n^th node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

思路：

#include <iostream>
#include <vector> 
using namespace std;
/*
 Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.
*/
/*
删除链表的倒数第n个节点 
使用两个指针来开始遍历 中间间隙可以为n，等到后一个节点达到末尾，删除前面的那个节点 
假如我们需要删除第N个节点，那么是的first和second之间的距离为n，等到 second的节点为Null,
那么我们就删除first->next节点即可 
*/

typedef struct list_node List;
struct list_node
{
	struct list_node* next;
	int value;
};

void print_list(List* list)
{
	List* tmp=list;
	while(tmp != NULL)
	{
		cout<<tmp->value<<endl;
		tmp = tmp->next; 
	}
}

/*
初始化List  将从1~n的数字插入到链表中 
*/
void Init_List(List*& head,int n)
{
	head = NULL;
	List* tmp;
	List* record;
	/*
	for(int i=1;i<=n;i++)
	{
		tmp = new List;
		tmp->next = head;
		tmp->value = i;
		head = tmp;
 
	}
	*/
	for(int i=1;i<=n;i++)
	{
		tmp = new List;
		tmp->next = NULL;
		tmp->value = i;
		if(head == NULL)
		{
			head = tmp;
			record = head;
		}
		else
		{
			record->next = tmp;
			record = tmp;
		}
	}
}

int Len_list(List* list)
{
	if(list == NULL)
		return 0;
	else
		return Len_list(list->next)+1;
}


void Remove_nth(List*&list ,int nth)
{
	List* first;
	List* second;
	int i;
	first = second = list;
	for(i=1;i<=nth && second !=NULL;i++)
		second = second->next;
	 
	while(second != NULL && second->next != NULL)
	{
		first = first->next;
		second = second->next;
	}
 
	if(first == list)
	{
		
		list = first->next;
		delete first;
	}
	else
	{
		second = first->next;
		first->next = second->next;
		delete second;	
	}
	
}

int main()
{
	List* head;
	Init_List(head,10);
	Remove_nth(head,3);
	
	print_list(head);
	return 0;
}