题目
Given a linked list, remove the n-th node from the end of list and return its head.
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.
Follow up:
Could you do this in one pass?
解法思路（一）
- 如果遍历两遍，这个问题很好解决，在第一次遍历的时候，就能“探明”整个链表的全部，要删除的节点在哪，就清楚了，第二次遍历的时候，把要删除的节点删除；
- 但是遍历一遍这个问题一样可以解决，具体的做法是：以 n 为一个固定的长度制作一个“滑动窗口”，“滑动窗口”的左端是 n 的前驱，右端是链表的结尾 null，以这个窗口，移动到链表的开头，窗口的左端指向虚拟头节点，右端和左端之间有 n 个节点，滑动这个窗口，直到右端点重新指向链表的结尾，左端点指向待删除的节点的前驱，这时，窗口的左端跨过待删除的节点，指向待删除的节点的后继，删除完成，一遍完成；
解法实现（一）
时间复杂度
- O(N)；
空间复杂度
- O(1)；
关键字
链表 双指针 滑动窗口
实现细节
- 引入了虚拟头节点后，直接返回
dummyHead.next；
class Solution19_1 {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode p = dummyHead;
ListNode q = dummyHead;
for(int i = 0; i <= n; i++) {
q = q.next;
}
while(q != null) {
q = q.next;
p = p.next;
}
p.next = p.next.next;
return dummyHead.next;
}
}
