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