leetcode19

题目

19 删除链表的倒数第N个节点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点
输入：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个节点，让fast先移动n步，然后让fast和slow同时移动，直到fast指向链表末尾，之后删掉slow所指向的节点就可以了。

• 设置初始位置后,先移动fast指针，直到两个节点的间隔为n

• 之后一起移动两个指针，直到fast到达末尾

class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *newHead = new ListNode(0, head);
        ListNode *prev = newHead, *cur = head;
        int step = 1; // prev和cur的间隔
        while (cur->next != nullptr)
        {
            if (step == n)
            {
                prev = prev->next;
            }
            else
            {
                step++;
            }
            cur = cur->next;
        }
        ListNode* tmp = prev->next;
        prev->next = prev->next->next;
        delete tmp;
        return newHead->next;
    }
};