題目描述
給定一個(gè)鏈表，刪除鏈表的倒數(shù)第?n?個(gè)節(jié)點(diǎn)攀隔，并且返回鏈表的頭結(jié)點(diǎn)皂贩。
示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個(gè)節(jié)點(diǎn)后，鏈表變?yōu)?1->2->3->5.
說明：
給定的?n?保證是有效的昆汹。
進(jìn)階：
你能嘗試使用一趟掃描實(shí)現(xiàn)嗎明刷？
題目解析:
采用雙重遍歷肯定是可以解決問題的，但是題目要求我們 一次遍歷解決問題筹煮，那我們的思路得散發(fā)一下遮精。
我們可以設(shè)想假設(shè)設(shè)定了雙指針p和q，當(dāng)q指向末尾的NULL時(shí)败潦，p和q之間相隔的元素個(gè)數(shù)為n時(shí)，那么刪除掉p的下一個(gè)指針就完成了要求准脂。
1.設(shè)置虛擬節(jié)點(diǎn)dummyHead指向head
2.設(shè)定雙指針p和q劫扒，初始都指向虛擬節(jié)點(diǎn)dummyHead
3.移動(dòng)q，直到p和q之間相隔的元素個(gè)數(shù)為n
4.同時(shí)移動(dòng)p與q狸膏，知道q指向的為NULL
5.將p的下一個(gè)節(jié)點(diǎn)指向下下一個(gè)節(jié)點(diǎn)沟饥。
public class Solution3 {
public ListNode removeNthFromEnd(ListNode head, int n) {
//創(chuàng)建一個(gè)虛擬頭結(jié)點(diǎn)
ListNode dummy = new ListNode(-1);
dummy.next =head;
ListNode fast = dummy;
ListNode slow = dummy;
while(fast !=null && n>-1){
fast = fast.next; n--;
}
while(fast!=null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
