1.jpg
2.jpg
struct ListNode {
int val;
ListNode* next;
ListNode(int x): val(x), next(nullptr) {}
};
/* 双指针法: fast and slow */
class Solution {
public:
ListNode* removeNthNode(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* fast = dummy;
ListNode* slow = dummy;
while(n-- && fast != nullptr) {
fast = fast->next; // fast指针先移动n步,slow指针暂时不动
}
fast = fast->next; // fast指针再向前移动一步，因为需要利用slow指针指向被删除节点的上一个节点,便于删除操作
// fast和slow指针同时移动相同步长,直到fast指向nullptr为止
while(fast != nullptr) {
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
return dummy->next;
}
};
