19.删除链表的倒数第N个节点 remove-nth-node-from-end-of-list

问题描述

19.删除链表的倒数第N个节点

解题思路

首先设置一个虚拟头节点pre，pre->next = head;

双指针法，考虑使用两个指针fast，slow，一快一慢，fast指针先前进n个位置，然后fast和slow一起遍历，当fast到达最后一个节点的时候，slow刚好位于要删除的节点的前一个节点。

代码

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