C++实现移除链表倒数第N个节点

# C++实现移除链表倒数第N个节点

## 目录
1. [问题描述](#问题描述)
2. [链表基础回顾](#链表基础回顾)
3. [解法一：两次遍历法](#解法一两次遍历法)
4. [解法二：双指针法](#解法二双指针法)
5. [完整代码实现](#完整代码实现)
6. [边界条件与测试用例](#边界条件与测试用例)
7. [复杂度分析](#复杂度分析)
8. [应用场景](#应用场景)
9. [总结](#总结)

## 问题描述
给定一个单向链表，要求删除链表的倒数第N个节点，并返回链表的头节点。例如：

输入：1->2->3->4->5, n = 2  
输出：1->2->3->5

## 链表基础回顾
```cpp
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

• 单向链表由节点构成，每个节点包含值和指向下一个节点的指针
• 链表操作需注意指针的指向关系和内存管理

解法一：两次遍历法

算法步骤

1. 第一次遍历计算链表长度L
2. 计算待删除节点的正序位置：L - n
3. 第二次遍历定位到目标节点的前驱节点
4. 修改指针完成删除

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    int length = 0;
    
    // 第一次遍历计算长度
    ListNode* curr = head;
    while (curr) {
        length++;
        curr = curr->next;
    }
    
    // 定位到待删除节点的前驱
    curr = &dummy;
    for (int i = 0; i < length - n; i++) {
        curr = curr->next;
    }
    
    // 执行删除
    ListNode* toDelete = curr->next;
    curr->next = curr->next->next;
    delete toDelete; // 防止内存泄漏
    
    return dummy.next;
}

解法二：双指针法

算法思想

使用快慢指针实现单次遍历： - 快指针先移动n步 - 然后快慢指针同步移动 - 当快指针到达末尾时，慢指针指向待删除节点的前驱

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode *fast = &dummy, *slow = &dummy;
    
    // 快指针先移动n+1步
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }
    
    // 同步移动直到快指针到末尾
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }
    
    // 执行删除
    ListNode* toDelete = slow->next;
    slow->next = slow->next->next;
    delete toDelete;
    
    return dummy.next;
}

完整代码实现

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    // 双指针法实现
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0);
        dummy.next = head;
        ListNode *fast = &dummy, *slow = &dummy;
        
        for (int i = 0; i <= n; ++i) {
            fast = fast->next;
        }
        
        while (fast) {
            fast = fast->next;
            slow = slow->next;
        }
        
        ListNode* toDelete = slow->next;
        slow->next = slow->next->next;
        delete toDelete;
        
        return dummy.next;
    }
};

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << "->";
        head = head->next;
    }
    std::cout << "nullptr" << std::endl;
}

// 辅助函数：创建测试链表
ListNode* createList(std::initializer_list<int> vals) {
    ListNode dummy(0);
    ListNode* curr = &dummy;
    for (int val : vals) {
        curr->next = new ListNode(val);
        curr = curr->next;
    }
    return dummy.next;
}

int main() {
    Solution solution;
    
    // 测试用例1
    ListNode* list1 = createList({1, 2, 3, 4, 5});
    std::cout << "Original list: ";
    printList(list1);
    list1 = solution.removeNthFromEnd(list1, 2);
    std::cout << "After removal: ";
    printList(list1);
    
    // 测试用例2
    ListNode* list2 = createList({1});
    list2 = solution.removeNthFromEnd(list2, 1);
    printList(list2); // 应输出 nullptr
    
    return 0;
}

边界条件与测试用例

复杂度分析

1. 两次遍历法：

   • 时间复杂度：O(L) 两次遍历，2L → O(L)
   • 空间复杂度：O(1)

2. 双指针法：

   • 时间复杂度：O(L) 单次遍历
   • 空间复杂度：O(1)

应用场景

1. 操作系统中的进程调度
2. 浏览器历史记录管理
3. 音乐播放列表操作
4. 大数据处理中的流式数据处理

总结

1. 双指针法是更优的解决方案，只需一次遍历
2. 使用哨兵节点(dummy node)可以简化头节点处理
3. 必须注意内存管理，特别是C++中的节点删除
4. 算法时间复杂度都是O(L)，但双指针法常数项更小

关键点：掌握快慢指针技巧是解决链表问题的关键，这种方法可以扩展到许多其他链表问题，如检测环、寻找中点等。 “`

这篇文章提供了约1900字的详细内容，包含： - 两种解法的完整实现 - 复杂度分析 - 边界条件处理 - 实际应用场景 - 可执行的测试代码 - 标准Markdown格式的排版