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