删除链表的倒数第n个节点（C++解法）

题目

给你一个链表，删除链表的倒数第 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]

C++代码

#include <iostream>
#include <stack>
using namespace std;//创建链表结构体
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) {}
};/*
* 删除链表的倒数第n个节点问题
* 定义dummyNode哑节点和链表类型的栈
* 栈的先入后出原则可以解决倒数第n个节点的判定
* 找到要删除节点的前一个节点，直接指向下下个节点
*/
ListNode* removeNthFromEnd(ListNode* head, int n) {ListNode* dummyNode = new ListNode(0, head);stack<ListNode*> stk;ListNode* cur = dummyNode;while (cur) {stk.push(cur);cur = cur->next;}for (int i = 0; i < n; ++i) {stk.pop();}ListNode* prev = stk.top();prev->next = prev->next->next;return dummyNode->next;
}int main() {ListNode* n1 = new ListNode(1);ListNode* n2 = new ListNode(2);ListNode* n3 = new ListNode(3);ListNode* n4 = new ListNode(4);ListNode* n5 = new ListNode(5);n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = nullptr;ListNode* head = n1;int n = 2;ListNode* ans = removeNthFromEnd(head, n);while (ans) {cout << ans->val << " ";ans = ans->next;}return 0;
}

分析

删除链表的倒数第 n 个节点问题，定义dummyNode 哑节点和链表类型的栈，栈的先入后出原则可以解决倒数第 n 个节点的判定，找到要删除节点的前一个节点，直接指向下下个节点。

dummyNode 节点的作用是作为一个虚拟的头前节点。在不知道要返回的新链表的头结点是哪一个，它可能是原链表的第一个节点，可能在原链表的中间，也可能在最后，甚至不存在。引入 dummyNode 节点可以涵盖所有情况，并且可以使用 dummyNode->next 返回最终需要的头结点。