力扣-19题删除链表的倒数第N个结点（C++）- 双指针

浅浅的花香味﹌ 2022-09-05 11:25 55阅读 0赞

题目链接：[https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/][https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]  
题目如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]

/**
     * 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:
        ListNode* removeNthFromEnd(ListNode* head, int n) {
        
            ListNode* dummyHead=new ListNode(-1);//头节点可能发生改变
            dummyHead->next=head;
            ListNode *slow=dummyHead,*fast=dummyHead;
    
            for(int i=0;i<n+1;i++)//fast先走n+1步，因为只有这样同时移动时slow才能指向删除节点的上一个节点（方便做删除操作）
                fast=fast->next;
    
            while(fast!=NULL){
        
                fast=fast->next;
                slow=slow->next;
            }
    
            slow->next=slow->next->next;
    
            return dummyHead->next;
        }
    };

[https_leetcode-cn.com_problems_remove-nth-node-from-end-of-list]: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70]: /images/20220829/4698d1075f0a47e9988430a34dec9bf0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNDY3Njcw_size_16_color_FFFFFF_t_70 1]: /images/20220829/ce563fb81aa744ea8d0c5aed0c05c04c.png