从尾到头打印单链表

voidFromTailToHeadPrint(SListNode*&head){stack<SListNode*>s;SListNode*cur=head;while(cur){s.push(cur);cur=cur->_next;}while(!s.empty()){cout<<s.top()->_data<<"->";s.pop();}cout<<""<<endl;}



2.删除一个无头单链表的非尾节点

voidErase(SListNode*&head,SListNode*pos){//分情况：空节点、一个节点、两个节点、三个节点if(head==NULL||pos==NULL){return;}if(head==pos){free(head);head=NULL;return;}SListNode*cur=head;while(cur){SListNode*next=cur->_next;if(next==pos){//若只有两个节点，pos=next,nextnext=NULL，cur->_next=nextnext;//（即使题设未说明删除非尾节点）依然可以删除成功。SListNode*nextnext=next->_next;cur->_next=nextnext;free(next);next=NULL;}cur=cur->_next;}}



3.逆置、反转单链表

voidReverse(SListNode*&head){if(head==NULL){return;}SListNode*cur=head;SListNode*next=NULL;while(cur){SListNode*tmp=cur;cur=cur->_next;tmp->_next=next;next=tmp;head=tmp;}}



4.单链表冒泡排序

voidBubbleSort(SListNode*&head){//空节点或一个节点直接返回if(head==NULL||head->_next==NULL){return;}SListNode*begin=head;SListNode*cur=head;while(begin->_next){while(cur->_next){if(cur->_data>cur->_next->_data){swap(cur->_data,cur->_next->_data);}cur=cur->_next;}begin=begin->_next;}}



5.查找单链表的中间节点，要求只能遍历一次链表

SListNode*FindMiddle(SListNode*&head){if(head==NULL){returnNULL;}SListNode*slow=head;SListNode*fast=head;while(fast->_next){if(fast->_next){fast=fast->_next;if(fast->_next){fast=fast->_next;}else{returnslow;}slow=slow->_next;}else{returnNULL;}}returnslow;}



6.查找单链表的倒数第k个节点，要求只能遍历一次链表

SListNode*FindLastK(SListNode*&head,intk){assert(k>0);if(head==NULL){returnNULL;}SListNode*slow=head;SListNode*fast=head;while(k--){if(fast->_next){fast=fast->_next;}else{returnNULL;}}slow=slow->_next;while(fast->_next){fast=fast->_next;slow=slow->_next;}returnslow;}