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