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.
題目
刪除鏈表倒數(shù)第n個元素
思路
經典題目
快慢指針法脓规，快指針先走n步抖甘，再和慢指針一起走，當快指針走到最后一個元素時眷蜓，慢指針指向倒數(shù)第n個元素烈疚。
這里有一個技巧：就是建立虛擬頭結點炕檩，快慢指針從虛擬頭結點開始遍歷，這樣最后慢指針會指向倒數(shù)第n個元素的前驅坚洽，傳統(tǒng)方法刪除即可戈稿。
若從head開始遍歷，則需要考慮n=1的情況讶舰，也就是慢指針指向最后一個節(jié)點并刪除鞍盗。
代碼
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head.next == null)
return null;
ListNode dummy = new ListNode(0);
ListNode fast = dummy, slow = dummy;
dummy.next = head;
for (int i = 0; i < n; ++i)
fast = fast.next;
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return dummy.next;
}
