算法描述 :
給定一個(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)嗎婚肆？
算法實(shí)現(xiàn) :
Java實(shí)現(xiàn) :
/**
* 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) {
if (head==null) {
return null;
}
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head; // 虛擬頭結(jié)點(diǎn)指向head
int len =0; // 鏈表長(zhǎng)度
ListNode p = dummyHead;
while (p.next!=null) {
len++;
p = p.next;
}
p = dummyHead;
for (int i=0;i<len-n;i++) {
p = p.next;
} // p指向待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
p.next = p.next.next; // 跳過待刪除的節(jié)點(diǎn),直接指向下一個(gè)節(jié)點(diǎn)
return dummyHead.next;
}
}
