链表刷题

1

为了熟悉链表使用，这题使用双指针法

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 创建一个虚拟头节点，指向链表的头节点
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;  // 快指针
        ListNode* second = dummy; // 慢指针

        // 快指针先走 n 步
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }

        // 快慢指针一起走，直到快指针到达链表末尾
        while (first) {
            first = first->next;
            second = second->next;
        }

        // 删除倒数第 n 个节点
        second->next = second->next->next;

        // 返回新链表的头节点
        ListNode* ans = dummy->next;
        delete dummy;  // 释放虚拟头节点的内存
        return ans;
    }
};