Leetcode题目链接：19. 删除链表的倒数第 N 个结点

题目描述

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

题目示例

示例一

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

示例二

输入：head = [1], n = 1
输出：[]

示例三

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

解题思路

快慢指针

• 定义指针

  • 定义虚拟头节点dummyHead，其next指针域指向实际头节点head，即dummyHead->next = head

  • 定义慢指针slow和快指针fast，初始化指向虚拟头节点dummyHead

  • 在删除某个节点时，操作指针（slow）需要指向待删除节点的前一个位置，即n++使得fast指针和slow指针之间相差n+1个位置

• 指针后移

  • 执行第一个while循环，使得fast指针不断向后移动，当移动n个位置后（实际为n+1个位置）或fast指针已经指向为空（即当前位置没有元素）时退出循环，此时fast指针和slow指针之间相差n+1个位置

  • 执行第二个while循环，使得fast指针与slow指针同时移动，直到fast指针已经指向为空，此时slow指针指向的便是链表的倒数第N+1个节点

• 删除元素

  • 使用temp临时指针记录待删除元素的前驱指针，即slow->next

  • 更新指针指向，即将倒数第N+1个元素的指针域直接指向倒数第N-1个元素，即slow->next = slow->next->next

  • 手动释放内存，即delete temp

• 返回头节点

我的答案

/**
 * 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();
        ListNode *slow = dummyHead, *fast = dummyHead;
        dummyHead->next = head;
        n++;
        //指针后移
        while(n-- && fast != nullptr) {
            fast = fast->next;
        }
        while(fast != nullptr){
            fast = fast->next;
            slow = slow->next;
        }
        //删除元素
        ListNode* temp = slow->next;
        slow->next = slow->next->next;
        delete temp;

        return dummyHead->next;
    }
};

提交结果