删除链表的倒数第n个节点（C++解法）-Toy模板网

这篇具有很好参考价值的文章主要介绍了删除链表的倒数第n个节点（C++解法）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

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

示例 1：

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

输入：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 返回最终需要的头结点。文章来源地址https://www.toymoban.com/news/detail-737925.html

到了这里，关于删除链表的倒数第n个节点（C++解法）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！