1. 原題鏈接：https://leetcode.com/problems/remove-nth-node-from-end-of-list/
2. 解題思路
- 利用啞節點將邊界case轉化為一般case
- 倒數第n個，也就是順數第(鏈表總長度-n+1)個
- 由于需要洗掉順數第(總長度-n+1)個，因此需要知道順數第(總長度-n)個節點的位置，該位置可以通過快慢指標得到
3. 演算法
- 創建包含啞節點的鏈表，這樣可以避免處理洗掉頭結點和只有一個節點的這兩種情況
- fast指標先移動n步，然后fast和slow指標同時移動，一直到fast指標指向最后一個節點時，slow指標剛好指向第(總長度-n)個節點
- 現在slow指標的下一個節點就是需要洗掉的節點
4. 實作
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(-1);
dummy.next = head;
ListNode *fast = &dummy;
ListNode *slow = &dummy;
for(int i = 0; i < n; i++){ //移動[n]步
fast = fast->next;
}
while(fast->next != NULL){ //移動[鏈表長度-n]步
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummy.next;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88251.html
標籤：其他
上一篇：變態跳臺階
下一篇：https服務關于埠的使用問題