C++實現鏈表常見面試題

C+實現鏈表的常見面試題

刪除非尾節點：

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;
	}

反轉（逆序）鏈表：

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;
	}
	
}

在當前節點前插入一個數據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;
	}

查找鏈表的中間節點：

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

}

刪除單鏈表的倒數第k個節點(k > 1 && k < 鏈表的總長度)：

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指向的是倒數第k個節點
		Node* del=list2->_next;
		list2->_data=del->_data;//將list2后面的數覆蓋到list2，刪除list2后面的節點
		list2->_next=del->_next;
		delete del;
	}

鏈表的帶環問題：

1.檢查鏈表是否帶環，若帶環返回相遇點，不帶環則返回空

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.求環的長度

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.獲取環入口點

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

刪除鏈表中指定的數字

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;
	}
	
}

刪除鏈表中所有指定的數字

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指向下一個節點
				delete del;
			}
		}
		else
		{
			prev=cur;
			cur=cur->_next;
		}
	}
}

查找指定數字并返回所在位置

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

Node 結構體

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

SList 類

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