C+实现链表的常见面试题

删除非尾节点：

voidSList::EraseNotTail(Node*pos){Node*del=NULL;pos->_data=pos->_next->_data;del=pos->_next;pos->_next=pos->_next->_next;deletedel;del=NULL;}

反转（逆序）链表：

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

排序链表（冒泡）：

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

在当前节点前插入一个数据x：

voidSList::InsertFrontNode(Node*pos,DataTyped){Node*newnode=newNode(d);newnode->_next=pos->_next;pos->_next=newnode;DataTypetmp=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;}returnslow;}

删除单链表的倒数第k个节点(k > 1 && k < 链表的总长度)：

voidSList::DelKNode(intk){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;deletedel;}

链表的带环问题：

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)returns1;}returnNULL;}

2.求环的长度

intSList::GetCircleLength(Node*meetNode){if(meetNode==NULL){return0;}Node*cur=meetNode;intcount=0;do{cur=cur->_next;count++;}while(cur!=meetNode);returncount;}

3.获取环入口点

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

删除链表中指定的数字

voidSList::Remove(constDataType&d){Node*del=Find(d);if(del==_head){_head=_head->_next;deletedel;return;}else{Node*cur=_head;while(cur->_next!=del){cur=cur->_next;}if(del==_tail){_tail=cur;}cur->_next=del->_next;deletedel;}}

删除链表中所有指定的数字

voidSList::RemoveAll(constDataType&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;//deletedel;}else{Node*del=cur;if(cur==_tail){_tail=prev;}prev->_next=cur->_next;cur=prev->_next;//cur指向下一个节点deletedel;}}else{prev=cur;cur=cur->_next;}}}

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

Node*SList::Find(constDataType&d){Node*cur=_head;while(cur){if(cur->_data==d)returncur;cur=cur->_next;}returnNULL;}

Node 结构体

structNode{Node(constDataType&d):_data(d),_next(NULL){}DataType_data;structNode*_next;};

SList 类

classSList{protected:Node*_head;Node*_tail;};