Leetcode19. Remove Nth Node From End of List
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?
解析
设想假设设定了双指针 p 和q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉p 的下一个指针就完成了要求。
- 设置虚拟节点
dummyHead指向head - 设定双指针
p和q，初始都指向虚拟节点dummyHead - 移动
q，直到p与q之间相隔的元素个数为n - 同时移动
p与q，直到q指向的为NULL - 将
p的下一个节点指向下下个节点
Java
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode first = dummy;
ListNode second = dummy;
// Advances first pointer so that the gap between first and second is n nodes apart
for (int i = 1; i <= n + 1; i++) {
first = first.next;
}
// Move first to the end, maintaining the gap
while (first != null) {
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}