当前位置：首页 > article >正文

【练习】【链表】力扣热题100 19. 删除链表的倒数第 N 个结点

article 2025/3/6 1:52:23

题目

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

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

示例 1：

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

输出：[1,2,3,5]

示例 2：

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

输出：[]

示例 3：

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

输出：[1]

来源：力扣热题100 19. 删除链表的倒数第 N 个结点

思路（注意事项）

三个指针。
pre：删除节点的前置指针
p：删除节点
q ：距离指针

但也可以简化为两个指针，另外需要在输入的链表上加上头节点。（详见ds简化版）

纯代码

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int sum = 0;
        ListNode *t = head;
        while (t != nullptr) sum ++, t = t ->next;
        if (n == sum) return head -> next;

        if (head == nullptr || head -> next == nullptr) return nullptr;
        ListNode *pre = head, *p = pre -> next, *q = p;

        while (n --) q = q -> next;

        while (q != nullptr)
        {
            q = q -> next;
            p = p -> next;
            pre = pre -> next;
        }

        pre -> next = p -> next;
        return head;
    }
};

题解（加注释）

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 计算链表的长度
        int length = 0;
        ListNode* t = head;
        while (t != nullptr) {
            length++;
            t = t->next;
        }

        // 如果删除的是头节点，直接返回头节点的下一个节点
        if (n == length) {
            return head->next;
        }

        // 如果链表为空或只有一个节点，返回空链表
        if (head == nullptr || head->next == nullptr) {
            return nullptr;
        }

        // 初始化指针
        ListNode* pre = head; // 指向要删除节点的前一个节点
        ListNode* p = pre->next; // 指向要删除的节点
        ListNode* q = p; // 用于遍历的指针

        // 将 q 移动到第 n 个节点
        while (n--) {
            q = q->next;
        }

        // 移动 pre、p 和 q，直到 q 到达链表末尾
        while (q != nullptr) {
            q = q->next;
            p = p->next;
            pre = pre->next;
        }

        // 删除节点
        pre->next = p->next;

        return head;
    }
};

（详见ds简化版）

题解（ds简化）

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* L = new ListNode(0); // 创建虚拟头节点
        L->next = head;
        ListNode* fast = L;
        ListNode* slow = L;

        // 快指针先移动 n 步
        for (int i = 0; i <= n; i++) fast = fast->next;

        // 同时移动快慢指针，直到快指针到达链表末尾
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        // 删除节点
        slow->next = slow->next->next;

        return L->next; // 返回结果链表的头节点
    }
};