leetcode 力扣算法题 快慢指针 双指针 19.删除链表的倒数第n个结点

题目要求

• 给你一个链表，删除链表的倒数第n个结点，并且返回链表的头结点。

题目示例

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：
输入：head = [1], n = 1
输出：[]

示例 3：
输入：head = [1,2], n = 1
输出：[1]

解题思路

• 如果我们需要用一次扫描就完成这个操作，那么我们首先想到的一定是需要多个指针（结点）互相配合，才有可能一次扫描删除指定结点的操作。
• 那么继续思考，倒数第n个结点，输入会给出n的值，那么我们需要考虑的是怎么根据给出的这个n值来定位到我们的目标结点

从题目中的已知出发思考

寻找目标结点

• 我们可以设想用两个指针来寻找目标结点，假设链表长度一共为lenth，倒数第n个就是正数第lenth-n+1个，那么也就是说需要一个指向头结点的指针从头结点开始走lenth-n步就走到了需要删除的那个结点。

条件转换

• 上述的寻找思路我们发现需要遍历两次链表才能实现，但是在要求遍历一次时，我们就可以想到“快慢指针”（双指针）

核心思路

• 定义一个快指针和一个慢指针都先指向头结点，然后快指针先走n步，然后快、慢指针同时走，发现当快指针走到链表结尾的时候，慢指针就刚好走到了要删除结点的前一个结点，那么此时只需要将慢指针的next指向慢指针next的next即可完成删除操作（就本题来说可以忽略释放删除结点这个操作，当然释放一下也可以）

需要注意的点

• 如果采用上面的思路操作的话，那么就会发现示例二是不能通过的，因为会出现野指针的问题。

改进建议

• 创建一个前驱结点，快、慢指针都从前驱结点开始遍历，这样就可以成功的删除头结点并返回NULL了。

完整代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* prehead = new ListNode(0);
        prehead->next = head;
        ListNode* slow = prehead;
        ListNode* fast = prehead;
        while(n--){
            fast = fast->next;
        }
        while(fast->next!=nullptr){
            fast = fast->next;
            slow = slow->next;
        }
       
        slow->next = slow->next->next;
        
        return prehead->next;
    }
};

提交结果