C++ 删除链表倒数第 N 个节点：双指针与虚拟头节点法

星野

发布时间：2026-10-13| 2人浏览过

原创

在 C++ 数据结构与算法面试中，“删除链表的倒数第 N 个结点”是一道经典高频题。解决此问题的关键在于准确定位目标节点的前驱节点。本文对比了两次遍历法与一次遍历的双指针法，并展示了如何使用虚拟头节点（Dummy Node）简化对头节点的特殊判断，确保代码的健壮性与简洁性。

题目要求与输入示例

给定一个单链表的头节点 `head` 和一个整数 `n`，请删除链表的倒数第 `n` 个结点，并返回链表的头节点。

例如，若输入链表为 [1,2,3,4,5]，n=2，则输出 [1,2,3,5]。注意，当需要删除的是头节点时（如 n=5），直接使用原头指针可能导致逻辑混乱，因此引入辅助结构至关重要。

方法一：两次遍历法

第 1 步：获取链表长度

目的：确定链表中节点的总数 L，从而计算出倒数第 N 个节点正数是第几个。

操作：从头节点开始遍历链表，统计节点数量直到 head 为 null。

第 2 步：定位并删除目标节点

目的：找到待删除节点的前驱节点，修改其指针域。

操作：再次从链表头部开始遍历，走到第 L - n + 1 个节点（即待删节点的前驱）。此时将该节点的 next 指针指向其下下个节点 cur->next->next。

关键技巧：使用哑节点（dummy node）。创建一个虚拟头节点，其 next 指向实际头节点。这样即使删除的是原头节点，逻辑依然统一，无需单独判断 head 是否被删除。

/**
 * 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:
    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;
        
        // 移动 cur 到待删除节点的前驱位置
        // 倒数第 N 个是正数第 L-n+1 个，前驱即在它前面一位
        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;
    }
};

方法二：一次遍历双指针法

第 1 步：初始化双指针

目的：建立两个指针之间的固定间距，通过一次移动同步定位。

操作：同样创建虚拟头节点 dummyHead。设置快慢指针 p 和 q，初始均指向 dummyHead。

第 2 步：分离指针间距

目的：让快指针比慢指针多走 n 步。

操作：先移动 q 指针前进 n + 1 步。此时 p 和 q 之间恰好相隔 n 个节点（注意这里是指中间夹着的节点数，因为是从 dummy 开始的偏移量设计，具体步数可根据实现微调，通常向前挪 n+1 步是为了让 q 停在第 n+1 个节点上，或者根据循环条件调整）。

注：常见实现中，若 q 先走 n 步，则最后 p 会停在待删节点的前驱；若 q 走 n+1 步，需确保边界不越界。

第 3 步：同步移动直至结尾

目的：当快指针到达末尾时，慢指针自然位于待删节点的前驱。

操作：同时移动 p 和 q，直到 q 指向 NULL。

第 4 步：删除节点

目的：断开链接并清理内存。

操作：此时 p 指向待删节点的前驱。p->next 即为要删除的节点。保存该节点以便后续释放，将 p->next 指向 p->next->next，最后删除缓存的节点对象。

/**
 * 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(0);
        dummyHead->next = head;

        ListNode* p = dummyHead;
        ListNode* q = dummyHead;
        
        // 先让 q 向前走 n + 1 步
        // 这样当 q 到达末尾(NULL)时，p 正好在待删除节点的前一个节点
        for( int i = 0 ; i < n + 1 ; i ++ ){
            q = q->next;
        }
        
        // 同时移动，直到 q 为空
        while(q){
            p = p->next;
            q = q->next;
        }
        
        // p->next 就是需要删除的节点
        ListNode* delNode = p->next;
        p->next = delNode->next;
        
        // 释放被删除节点的内存
        delete delNode;
        
        // 获取新的头节点并释放虚拟头节点
        ListNode* retNode = dummyHead->next;
        delete dummyHead;
        
        return retNode;
    }
};