（力扣）删除链表的倒数第N个节点 C++-三种方法

时间：2024-03-27 15:00:36

（1）方法一：计算链表长度

  • 创建一个虚拟节点来处理删除头节点的情况
  • 通过计算链表的长度确定要删除节点的位置。
  • 使用双指针中的一个指针，移动到要删除节点的前一个位置。
  • 将指针后面的节点跳过，完成删除操作。
  • 整体思路是通过遍历链表和双指针的移动，定位到要删除的节点，并进行删除操作。
class Solution {
public:
    // 获取链表的长度
    int getLength(ListNode* head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head); // 创建一个虚拟节点，方便处理头节点的情况
        int length = getLength(head); // 获取链表的长度
        ListNode* cur = dummy; // 当前节点指针指向虚拟节点
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next; // 移动指针到要删除节点的前一个节点
        }
        cur->next = cur->next->next; // 跳过要删除的节点，将当前节点的下一个指针指向下下个节点
        ListNode* ans = dummy->next; // 获取删除节点后的链表头节点
        delete dummy; // 释放虚拟节点的内存
        return ans; // 返回新链表的头节点
    }
};

（2）方法二：栈

  • 在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 nnn 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点。
  • 相当于通过栈的辅助，找到了那个节点
  • 注意：找到的不是那个节点的值，而是要删除的倒数第n个节点的指针
  • 栈存储的是指针，即链表中每个节点的地址。通过栈的pop操作，我们可以访问到栈顶元素，即要删除的倒数第n个节点的前一个节点。该节点的next指针指向倒数第n个节点。
  • 通过栈顶元素的指针，我们可以修改链表结构，将倒数第n个节点跳过，让前一个节点的next指针指向倒数第n个节点的下一个节点。
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head); // 创建一个虚拟节点，方便处理头节点的情况
        stack<ListNode*> stk; // 创建一个栈，用来保存遍历过的节点
        ListNode* cur = dummy; // 当前节点指针指向虚拟节点
        while (cur) {
            stk.push(cur); // 将当前节点压入栈中
            cur = cur->next; // 移动到下一个节点
        }
        for (int i = 0; i < n; ++i) {
            stk.pop(); // 从栈中弹出n个节点，即倒数第n个节点的前一个节点
        }
        ListNode* prev = stk.top(); // 获取倒数第n个节点的前一个节点
        prev->next = prev->next->next; // 跳过倒数第n个节点，将前一个节点的next指针指向下下个节点
        ListNode* ans = dummy->next; // 获取删除节点后的链表头节点
        delete dummy; // 释放虚拟节点的内存
        return ans; // 返回新链表的头节点
    }
};

（3）方法三：双指针

  • 创建一个虚拟节点(dummy)，并将其指向链表的头节点。这样做是为了应对特殊情况，如果需要删除的节点是头节点，我们可以通过虚拟节点来处理。
  • 接下来，初始化两个指针，一个是first指针，指向链表的头节点，另一个是second指针，指向虚拟节点(dummy)。
  • 然后，我们用第一个指针(first)先向前移动n个位置。这样，当第一个指针(first)到达链表的末尾时，第二个指针(second)指向的节点就是要删除的倒数第n个节点的前一个节点。
  • 接着，我们用两个指针共同向前移动，直到第一个指针(first)到达链表的末尾。这样，第二个指针(second)就指向了要删除的倒数第n个节点的前一个节点。
  • 最后，修改第二个指针(second)的next指针，将其指向要删除的倒数第n个节点的下一个节点，从而实现了删除操作。返回处理后的链表的头节点，并释放虚拟节点(dummy)的内存。
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head); // 创建一个虚拟节点dummy，值为0，指向head
        ListNode* first = head; // 初始化第一个指针指向head
        ListNode* second = dummy; // 初始化第二个指针指向dummy
        for (int i = 0; i < n; i++) {
            first = first->next; // 第一个指针向前移动n个位置
        }
        while (first) {
            first = first->next; // 第一个指针向前移动直到末尾
            second = second->next; // 第二个指针向前移动
        }
        second->next = second->next->next; // 删除第二个指针的下一个节点
        ListNode* ans = dummy->next; // 获取链表的头节点
        delete dummy; // 释放虚拟节点的内存
        return ans; // 返回处理后的链表
    }
};

相关文章