删除链表的倒数第N个结点

题目链接

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

示例:

20220113090305-2022-01-13-09-03-06

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

思路

解法一：

  1. 使用虚拟节点指向 head；
  2. 使用快慢指针移动，其中快指针比慢指针先移动 n 个元素；
  3. 快慢指针一块移动，直至到链表结尾；
  4. 删除慢指针的下一个节点。
class Solution
{
public:
    ListNode *removeNthFromEnd(ListNode *head, int n)
    {
        ListNode *dumpyNode = new ListNode(-1, head);
        ListNode *fast = head, *slow = dumpyNode;

        while (n-- > 0)
        {
            fast = fast->next;
        }

        while (fast != nullptr) 
        {
            fast = fast->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return dumpyNode->next;
    }
};