问题描述
给定一个链表，删除链表的倒数第N个节点，并且返回链表的头结点。
实例
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
进阶
你能尝试使用一趟扫描实现么？
首先是普通的解法。
删除节点怎么实现呢?假设链表按x->y->z排列,要删除第y个节点，就是x.next = x.next.next ,即要找到被删除节点的上一个节点。
那么如何找到被删除的节点y的上一个节点x呢？先通过一轮遍历，获得链表长度length，当前被删除节点的序号则是 length-n+1，前一个节点x的序号就是length-n 。在这里可以用一个指针指向头结点，从头节点一路next,一步一步最终指向x节点，从头节点head走到x要这一过程经过length-n-1步。
这样大致的思路就出来了，但是还要考虑到几个特殊情况，比如链表长度可能为1或者要删除的节点就是头结点，这样就不存在前一节点了。
代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int length = 1;
ListNode temp=new ListNode(head.val);
temp.next = head.next;
while(temp.next != null)
{
length ++;
temp=temp.next;
}
if(length<=1)
{
return null;
}
length= length-n-1;//指定删除节点的前一个节点
if(length<0)
{
return head.next;
}
temp = head;
while(length!=0)
{
length--;
temp=temp.next;
}
temp.next = temp.next.next;
return head;
}
}
之后上网看别人的思路，解决了如何用一次遍历来完成删除。
参考链接
思路：创建一个temp节点，让temp.next =head。让head先走n步，这样head和temp节点就相差n+1个节点，之后让head和temp一起往后移动，直到head移动到了NULL的时候，这时的temp移动到了倒数第n+1个节点的位置，之时候改变temp->next将他指向他的下一个节点的下一个节点，这样就是把倒数第n个节点给删掉了。
这个可以减少很多条件判断，并且可以只遍历一次就可以把节点删掉了。要注意一定是temp节点的next域指向head,不是直接等于head。
贴上这个博主的源码：
class Solution {
public:
/**
* @param head: The first node of linked list.
* @param n: An integer.
* @return: The head of linked list.
*/
ListNode *removeNthFromEnd(ListNode *head, int n) {
// write your code here
ListNode *del=new ListNode(0);
del->next=head;
ListNode *temp=del;
for(int i=0;i<n;i++){head=head->next;}
while(head!=NULL){head=head->next;temp=temp->next;}
temp->next=temp->next->next;
return del->next;
}
};
