1搞乏、題目描述
給定一個鏈表吧史，刪除鏈表的倒數(shù)第 n 個節(jié)點吠各，并且返回鏈表的頭結(jié)點。
示例：
給定一個鏈表: 1->2->3->4->5, 和 n = 2.
當(dāng)刪除了倒數(shù)第二個節(jié)點后欠动，鏈表變?yōu)?1->2->3->5.
2永乌、思路
雙指針，當(dāng)快的前進(jìn)n時具伍，慢的開始铆遭；當(dāng)快的到結(jié)尾時，慢的正好到可以刪除的那個節(jié)點前一個沿猜。
3枚荣、代碼實現(xiàn)（C++）
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 雙指針 相差N
ListNode* p1 = head;
ListNode* p2 = head;
for (int i = 0; i < n; i++) {
p2 = p2->next;
}
// 如果n == 鏈表的長度,即刪除頭結(jié)點, 此時 p2 == NULL
if (p2 == NULL) {
return head->next;
}
while (p2->next != NULL) { // 當(dāng)p2指向尾節(jié)點時，p1指向倒數(shù)第n個節(jié)點的前一個節(jié)點
p1 = p1->next;
p2 = p2->next;
}
p1->next = p1->next->next;
return head;
}
};
