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+1个节点，令p和q间的距离为n+1，同时由于本题需要自己手动附加头节点，所以初始时可以令p指向附加头节点，q指向正数第n个节点，同时平移指针p和指针q，当指针q指向链表最后一个节点时，指针p恰好指向链表倒数第n+1个节点，即倒数第n个节点的前驱节点。该算法的时间复杂度为O(n)，且只需遍历链表一次；空间复杂度为O(1).
代码如下：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode first = new ListNode(0); // 附加头结点
first.next = head;
ListNode p = first;
ListNode q = first.next;
for(int i = 1; i < n; i++) // 将q从第1个节点移动到第n个结点
q = q.next;
while(q.next != null)
{
p = p.next;
q = q.next;
}
p.next = p.next.next;
return first.next;
}
}
