題目描述
給定一個鏈表，刪除鏈表的倒數(shù)第 n 個節(jié)點卷玉，并且返回鏈表的頭結(jié)點芋膘。
相關(guān)話題：?鏈表祭钉、雙指針???難度：?中等
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當刪除了倒數(shù)第二個節(jié)點后，鏈表變?yōu)?1->2->3->5.
說明：
給定的 n 保證是有效的它改。
進階：
你能嘗試使用一趟掃描實現(xiàn)嗎疤孕？
思路：
- 定義兩個指針
p和q，一開始p和q指針都指向demmy節(jié)點搔课，首先先讓q指針走n步(示例n=2)胰柑，如下圖。
- 然后
p和q指針同時前進爬泥，直至q指針到達最后一個節(jié)點柬讨，如下圖。
此時袍啡，p指針就是待刪除節(jié)點的前驅(qū)踩官。
（該題是要刪除節(jié)點，所以我們要想辦法知道待刪除節(jié)點的前驅(qū)境输，對于第一個節(jié)點蔗牡，它沒有前驅(qū)，我們就要給它制造前驅(qū)dummy嗅剖，以使得所有節(jié)點都統(tǒng)一）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
head = dummy;
ListNode p = head;
ListNode q = head;
//q先走n步
while((n--) != 0){
q = q.next;
}
while(q.next != null){
p = p.next;
q = q.next;
}
p.next = p.next.next;
return head.next;
}
}
