C+實(shí)現(xiàn)鏈表的常見(jiàn)面試題

創(chuàng)新互聯(lián)網(wǎng)站建設(shè)由有經(jīng)驗(yàn)的網(wǎng)站設(shè)計(jì)師、開(kāi)發(fā)人員和項(xiàng)目經(jīng)理組成的專業(yè)建站團(tuán)隊(duì)，負(fù)責(zé)網(wǎng)站視覺(jué)設(shè)計(jì)、用戶體驗(yàn)優(yōu)化、交互設(shè)計(jì)和前端開(kāi)發(fā)等方面的工作，以確保網(wǎng)站外觀精美、網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站設(shè)計(jì)易于使用并且具有良好的響應(yīng)性。

刪除非尾節(jié)點(diǎn)：

void SList::EraseNotTail(Node* pos)
	{
		Node* del=NULL;
		pos->_data=pos->_next->_data;
		del=pos->_next;
		pos->_next=pos->_next->_next;
		delete del;
		del=NULL;
	}

反轉(zhuǎn)（逆序）鏈表：

void SList::Reverse()
{
	if(_head==NULL)
		return;
	if(_head==_tail)
		return;
	Node* cur=NULL;
	Node* prev=NULL;
	Node* newnode=NULL;
	Node* tmp=_head;
	cur=_head;
	while(cur)
	{
		prev=cur;
		cur=cur->_next;
		prev->_next=newnode;
		newnode=prev;
	}
	_head=newnode;
	_tail=tmp;
}

排序鏈表（冒泡）：

void SList::BubbleSort()
{
	Node* cur=_head;
	Node* end=NULL;
	while(cur!=end)
	{
		while(cur&&(cur->_next!=end))
		{
			if(cur->_data>cur->_next->_data)
			{
				DataType tmp=cur->_data;
				cur->_data=cur->_next->_data;
				cur->_next->_data=tmp;
			}
			cur=cur->_next;
		}
		end=cur;
		cur=_head;
	}
	
}

在當(dāng)前節(jié)點(diǎn)前插入一個(gè)數(shù)據(jù)x：

void SList::InsertFrontNode(Node* pos, DataType d)
	{
		Node* newnode=new Node(d);
		newnode->_next=pos->_next;
		pos->_next=newnode;
		DataType tmp=pos->_data;
		pos->_data=pos->_next->_data;
		pos->_next->_data=tmp;
	}

查找鏈表的中間節(jié)點(diǎn)：

Node* SList::FindMidNode()
{
	Node* fast=_head;
	Node* slow=_head;
	while(fast&&(fast->_next!=NULL))
	{
		fast=fast->_next->_next;
		slow=slow->_next;
	}
	return slow;

}

刪除單鏈表的倒數(shù)第k個(gè)節(jié)點(diǎn)(k > 1 && k < 鏈表的總長(zhǎng)度)：

void SList::DelKNode(int k)
	{
		Node* list1=_head;
		Node* list2=_head;
		while(--k)
		{
			list1=list1->_next;
		}
		while(list1->_next!=NULL)
		{
			list1=list1->_next;
			list2=list2->_next;
		}//list2指向的是倒數(shù)第k個(gè)節(jié)點(diǎn)
		Node* del=list2->_next;
		list2->_data=del->_data;//將list2后面的數(shù)覆蓋到list2，刪除list2后面的節(jié)點(diǎn)
		list2->_next=del->_next;
		delete del;
	}

鏈表的帶環(huán)問(wèn)題：

1.檢查鏈表是否帶環(huán)，若帶環(huán)返回相遇點(diǎn)，不帶環(huán)則返回空

Node* SList::CheckCycle()
{
	Node* s1=_head;
	Node* s2=_head;
	while(s1&&(s1->_next!=NULL))
	{
		s1=s1->_next->_next;
		s2=s2->_next;
		if(s1==s2)
			return s1;
	}
	return NULL;
}

2.求環(huán)的長(zhǎng)度

int SList::GetCircleLength(Node* meetNode)
	{
		if(meetNode==NULL)
		{
			return 0;
		}
		Node* cur=meetNode;
		int count=0;
		do
		{
			cur=cur->_next;
			count++;
		}while(cur!=meetNode);
		return count;
	}

3.獲取環(huán)入口點(diǎn)

Node* SList::GetCycleEntryNode(Node* meetNode)
	{
		Node* entry=_head;
		Node* meet=meetNode;
		while(entry!=meet)
		{
			entry=entry->_next;
			meet=meet->_next;
		}
		return entry;
	}

刪除鏈表中指定的數(shù)字

void SList::Remove(const DataType& d)
{
	Node* del=Find(d);
	if(del==_head)
	{
		_head=_head->_next;
		delete del;
		return;
	}
	else
	{
		Node* cur=_head;
		while(cur->_next!=del)
		{
			cur=cur->_next;
		}
		if(del==_tail)
		{
			_tail=cur;
		}
		cur->_next=del->_next;
		delete del;
	}
	
}

刪除鏈表中所有指定的數(shù)字

void SList::RemoveAll(const DataType& d)
{
	Node* cur=_head;
	Node* prev=NULL;
	while(cur!=NULL)
	{
		if(cur->_data==d)
		{
			if(cur==_head)
			{

				Node* del=_head;
				_head=_head->_next;
				cur=_head;//
				delete del;
			}
			else
			{
				Node* del=cur;
				if(cur==_tail)
				{
					_tail=prev;
				}
				prev->_next=cur->_next;
				cur=prev->_next;//cur指向下一個(gè)節(jié)點(diǎn)
				delete del;
			}
		}
		else
		{
			prev=cur;
			cur=cur->_next;
		}
	}
}

查找指定數(shù)字并返回所在位置

Node* SList::Find(const DataType& d)
{
	Node* cur=_head;
	while(cur)
	{
		if(cur->_data==d)
			return cur;
		cur=cur->_next;
	}
	return NULL;
}

Node 結(jié)構(gòu)體

struct Node
{
	Node(const DataType& d)
		:_data(d)
		,_next(NULL)
	{}
	DataType _data;
	struct Node* _next;
};

SList 類

class SList
{
protected:
Node* _head;
Node* _tail;
};

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

新聞名稱：C++實(shí)現(xiàn)鏈表常見(jiàn)面試題-創(chuàng)新互聯(lián)
文章路徑：http://www.chinadenli.net/article38/djogsp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、企業(yè)網(wǎng)站制作、微信公眾號(hào)、搜索引擎優(yōu)化、網(wǎng)站營(yíng)銷、微信小程序

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)