题目链接:19. 删除链表的倒数第 N 个结点
思路:本题为双指针的经典应用,如果要删除倒数第n个结点,则先让fast移动n步,然后同时移动fast和slow,直至fast指向链表的最后一个结点,此时slow->next指向的结点即为要删除的结点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
//通过快慢指针,先让快指针移动n位,然后快慢指针同时移动,直到快指针指向最后一个结点
ListNode* removeNthFromEnd(ListNode* head, int n) {
//虚拟头指针_dummyHead,将实际头结点的删除与其他结点的删除逻辑统一
ListNode* _dummyHead = new ListNode(0, head);
ListNode* fastNode = _dummyHead;
ListNode* slowNode = _dummyHead;
while(n-- && fastNode != nullptr){
fastNode = fastNode->next;
}
while(fastNode->next != nullptr){
fastNode = fastNode->next;
slowNode= slowNode->next;
}
ListNode *tmp = slowNode->next;
slowNode->next = tmp->next;
delete tmp;
return _dummyHead->next;
}
};