单链表的应用--删除倒数第n个结点

单链表的应用--删除倒数第n个结点

  删除倒数第n个结点，利用前文写好的链表的框架，在链表类中补充DeleteNthFromEnd方法。

删除倒数第n个结点

一、问题分析二、代码分析

1.链表类2.链表方法 三、测试代码

1.主函数2.输出结果 四、源代码获取（免积分）

一、问题分析

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

二、代码分析 1.链表类

  在链表类中声明DeleteNthFromEnd方法。

template 
class linkList{
	public:
		linkList();//构造函数 
		~linkList();//析构函数 
		void Insert(int i ,ElemType x);//插入函数 
		void PrintList();//打印所有元素  
		int Length();//获取链表长度
		ElemType Get(int i) ;//按位查找，返回第i个元素的值
		int Locate(ElemType x) ;//按值查找，返回x在单链表中的位置
		ElemType Delete(int i) ;//删除第i个元素 
		void DeleteNthFromEnd(int n) ;//删除倒数第n个元素		
	private:
		Node* first; //头指针 
}; 

2.链表方法

  删除倒数第n个节点的方法（DeleteNthFromEnd）与删除某个节点的方法（Delete）类似，只不过是删除的索引位置不同。可以先遍历链表，求得链表的长度（Length），再根据提供的倒数第n个，找到要删除的结点的前驱，将前驱指向待删除的结点的后驱即可。

void linkList::DeleteNthFromEnd(int n)
{
	
	Node* p;
	p=first;
	int length=this->Length();//获取表长 
	
	int count=length-n;
	while(count--)
	{
		p=p->next;
	}
	Node* s=p->next; 
	p->next=p->next->next;//跳过倒数第n个结点 
	delete s;
}

三、测试代码 1.主函数

#include 
#include "linkList.h"
#include "linkList.cpp" 
using namespace std;

int  main() {
	linkList L;
	
	for(int i=1;i<=10;i++)
		L.Insert(i,i);
	cout<<"n原先链表的元素是:"< 
2.输出结果 
原先链表的元素是:
1 2 3 4 5 6 7 8 9 10
删除倒数第2个元素后的链表是:
1 2 3 4 5 6 7 8 10
再删除倒数第4个元素后的链表是:
1 2 3 4 5 7 8 10
再删除倒数第6个元素后的链表是:
1 2 4 5 7 8 10
 
四、源代码获取（免积分） 
删除单链表的倒数第n个节点
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5711310.html